[백준] 7562 나이트의 이동

문제

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

입력

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

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

출력

 

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

 

 

BFS문제입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-2,-1,1,2,2,1,-1,-2}, dx[] = {1,2,2,1,-1,-2,-2,-1}, INF = 987654321;

using namespace std;
int TC, I, a, b, c, d;
pi cur, des;
int bfs(pi from, pi to) {
	int v[301][301];
	mset(v);
	queue<pi>q;
	q.push(from);
	v[from.first][from.second] = 1;
	while (!q.empty()) {
		auto[y,x] = q.front();
		q.pop();
		rep(i, 8) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < I && nx >= 0 && nx < I && !v[ny][nx]) {
				v[ny][nx] = v[y][x] + 1;
				q.push({ ny,nx });
			}
		}
	}
	return v[to.first][to.second] - 1;
}
int main() {
	FAST;
	cin >> TC;
	while (TC--) {
		cin >> I;
		cin >> a >> b >> c >> d;
		cur = { a,b };
		des = { c,d };
		cout << bfs(cur, des) << "\n";
	}
}