[백준] [c++] 7562 번 나이트의 이동

나이트의 이동 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	13094	5795	4387	43.804%

문제

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

입력

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

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

출력

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

​

​

​

전형적인 bfs

#include <iostream>
#include <queue>
using namespace std;

int n;
int x, y;
int x2, y2;
int dx[] = { 1, 2,2,1,-1,-2,-2,-1 };
int dy[] = { -2,-1,1,2, 2, 1,-1,-2 };
int t;

int main() {
	cin >> t;
	while(t--) {
		int r=0;
		int arr[400][400] = { 0, };
		bool check[400][400] = { false, };
		queue<pair<int, int>> q;
		pair<int, int> p;
		bool cc = false;

		cin >> n;
		cin >> x >> y;
		cin >> x2 >> y2;

		if (x == x2&&y == y2) {
			cout << "0\n";
			continue;
		}

		q.push(make_pair(y, x));

		check[y][x] = true;

		while (!q.empty()) {
			p = q.front();
			q.pop();
			for (int i = 0; i<8; i++) {
				int ny = p.first + dy[i];
				int nx = p.second + dx[i];
				if (nx == x2&&ny == y2) {
					r = arr[p.first][p.second] + 1;
					cc = true;
					break;
				}
				else if (0 <= nx&&nx<n && 0 <= ny&&ny<n&&check[ny][nx] == false) {
					arr[ny][nx] = arr[p.first][p.second] + 1;
					check[ny][nx] = true;
					q.push(make_pair(ny, nx));
				}
			}
			if (cc) {
				cout << r << '\n';
				break;
			}
		}
	}
	return 0;
}