문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
int func(int x, int y) {
pair<int, int> pos;
pos.first = x;
pos.second = y;
queue<pair<int, int>> q;
q.push(make_pair(x, y));
while (!q.empty()) {
pair<int, int> current = q.front(); // 현재 처리할 node의 x,y값
int level = mymap[current.first][current.second]; // 현재 수행하려는 node의 level 값을 이미 알고 있다.
q.pop();
// 다음 위치가 a,b 라면
int moves[8][2] = { {2,1}, {2,-1}, {-2,1}, {-2,-1},{1,2},{-1,2},{1,-2},{-1,-2} };
for (int i = 0; i < 8; i++) {
int a = current.first + moves[i][0];
int b = current.second + moves[i][1];
// a,b가 잘못된 값이면 continue;
if (a >= XSIZE || b >= YSIZE || a < 0 || b < 0) {
continue;
}
if (mymap[a][b] != 0) {
continue;
}
if (a == Dx && b == Dy) return level + 1;
// a,b는 올바른 값. 논리전개
mymap[a][b] = level + 1;
pair<int, int> t(a, b);
q.push(t);
//q.push(make_pair(a, b));
}
// 찾았으면 종료 return
// 못찾았으면 map에 표시 tree level 을 map에 표시한다. 방문표시한다.
// 또 다음 위치에 대해 처리한다. 7번 처리한다.
}
}너비우선 탐색 (BFS), 큐 사용하여 풀기
