백준 소스코드 [C++] 7562 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

백준 소스코드 [C++] 7562 나이트의 이동

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool check[304][304];
int arr[304][304];
int n, m, startx, starty, destx, desty;
pair<int, int>pp, p[8] = { {-1,2} ,{-2,1}, {-2,-1}, {-1,-2} ,{2,1},{1,2},{1,-2},{2,-1} };
queue <pair<int, int> > q;
void bfs() {
	while (q.empty() != true) {
		pp = q.front();
		q.pop();

		if (pp.first == desty + 2 && pp.second == destx + 2) {
			while (q.empty() != true) q.pop();
			return;

		}
		for (int a = 0;a < 8;a++)
		if (check[pp.first + p[a].first][pp.second + p[a].second] == true)
		{
			check[pp.first + p[a].first][pp.second + p[a].second] = false;
			q.push({ pp.first + p[a].first, pp.second + p[a].second });
			arr[pp.first + p[a].first][pp.second + p[a].second]
				= min(arr[pp.first + p[a].first][pp.second + p[a].second], arr[pp.first][pp.second] + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int x = 0;x < n;x++) {
		cin >> m;
		cin >> startx >> starty;
		cin >> destx >> desty;
		for (int i = 0;i < 304;i++)for (int j = 0;j < 304;j++) check[i][j] = false;
		for (int i = 2;i < m+2;i++)for (int j = 2;j < m+2;j++) {
			check[i][j] = true;
			arr[i][j] = 987654321;
		}
		check[starty + 2][startx + 2] = false;
		arr[starty + 2][startx + 2] = 0;
		q.push({ starty + 2,startx + 2 });
		bfs();
		cout << arr[desty + 2][destx + 2] << '\n';
	}
	return 0;
}