나이트의 이동

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	32103	15716	11766	48.072%

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

구현

#include <bits/stdc++.h>
using namespace std;

int l; // (4<=l<=300)
int dist[300][300];
int testcase;

int dx[]{ -2,-1,1,2,2,1,-1,-2 };
int dy[]{  1,2,2,1,-1,-2,-2,-1};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> testcase;

	while (testcase--)
	{
		cin >> l;
		for (int i = 0; i < l; i++)
			fill(dist[i], dist[i] + l, -1);
		int x, y;
		cin >> x >> y;
		int dest_x, dest_y;
		cin >> dest_x >> dest_y;
		queue<pair<int, int>> Q;

		Q.push({ x,y });
		dist[x][y] = 0;

		while (!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			for (int dir = 0; dir < 8; dir++)
			{
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];

				if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
				if (dist[nx][ny] >= 0) continue;
				Q.push({ nx,ny });
				dist[nx][ny] = dist[cur.first][cur.second] + 1;
			}
		}

		cout << dist[dest_x][dest_y] << '\n';


	}

	return 0;
}