[c++][algoritm][baekjoon]7562 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

예제 입력 1 
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 
5
28
0

 

풀이

1)입력은

T: 테스트 케이스 

N : 체스판의 한변의 길이

sy,sx : 나이트 시작 좌표

ey,ex : 나이트 목적지 좌표 

2)풀이 핵심은 

dy,dx를 그림과 같이 이동하는 경우를 모두 표시해 두는 게 가장 중요하다. 

그리고 나머지는 기존 bfs를 이용한 방법과 동일 하다 

/*[baekjoon]7562 나이트의 이동*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int) 3e2)
int Map[MAXN+10][MAXN+10];
bool visited[MAXN+10][MAXN+10];
int T;//test case
int N;//Map size
int sy,sx,ey,ex;
int dy[]={2,1,2,1,-2,-1,-2,-1};
int dx[]={1,2,-1,-2,-1,-2,1,2};
bool inRange(int x, int y){
    return ( (x>=0) && (x<N) && (y>=0) && (y<N));
}

void BFS(int y, int x){
    int ny,nx;
    queue <pair<int,int>> q;
    q.push(make_pair(y,x));
    visited[y][x]=true;

    while(!q.empty()){
        y=q.front().first;
        x=q.front().second;
        q.pop();
        if((y==ey) && (x==ex)) break;
        for(int i=0; i<8; i++){
            ny=y+dy[i];
            nx=x+dx[i];
            if(inRange(ny,nx) && !visited[ny][nx]){
                visited[ny][nx]=true;
                Map[ny][nx]=Map[y][x]+1;
                q.push(make_pair(ny,nx));
            }
        }

    }

}
void InputData(){
    cin >> T;
}
void Solve(){
    for(int i=0; i<T; i++){
        cin >> N;
        cin >> sy >> sx >> ey >> ex ;
        BFS(sy,sx);
        cout << Map[ey][ex] << endl;
        memset(Map, false, sizeof(Map));
        memset(visited, false, sizeof(visited));
    }
}
int main(){
   InputData();
   Solve();
   return 0;
}
/*[baekjoon]7562 나이트의 이동*/