[210330][백준/BOJ] 7562번 나이트의 이동

문제

입출력

---

풀이

2178번 미로탐색이랑 비슷한 문제이다.
시작점부터 도착점까지의 거리를 BFS를 이용해서 구할 수 있다.

기존 BFS 문제들은 상하좌우에 접근하였지만 이 문제는 다른 8개의 접근 방법이 있으므로 이것만 주의해주면 쉽게 해결할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 302

int dist[SIZE][SIZE];
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, a, b, c, d;
		cin >> n >> a >> b >> c >> d;

		fill(dist[0], dist[0] + SIZE * SIZE, -1);

		queue<pair<int, int>>Q;
		dist[a][b] = 0;
		Q.push({ a,b });

		while (!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			for (int dir = 0; dir < 8; ++dir)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;
				if (dist[nx][ny] >= 0) continue;
				dist[nx][ny] = dist[cur.X][cur.Y] + 1;
				Q.push({ nx,ny });
			}
		}
		cout << dist[c][d] << '\n';
	}
}