백준 7562번 : 나이트의 이동

문제 링크 : www.acmicpc.net/problem/7562

내 풀이(2021.3.1.) : BFS

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pr;

int map[300][300] = { 0, };
int visit[300][300] = { 0, };
int dy[] = {-1,-2,-2,-1,1,2,2,1};
int dx[] = { -2,-1,1,2, -2,-1,1,2, };

void init() {
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			map[i][j] = 0;
			visit[i][j] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	for (int i = 0; i < N; i++)
	{
		init();
		int n; cin >> n;
		int fy, fx, ty, tx; cin >> fy >> fx >> ty >> tx;

		queue<pr> q;
		q.push(make_pair(fy, fx));
		visit[fy][fx] = 1;
		int cnt = 0;
		while (!q.empty()) {
			int sz = q.size();
			for (int j = 0; j < sz; j++)
			{
				pr cur = q.front(); q.pop();
				int cy = cur.first;
				int cx = cur.second;
				if (cy == ty && cx == tx) {
					cout << cnt << "\n";
					q = queue<pr>();
					break;
				}
				for (int j = 0; j < 8; j++)
				{
					int ny = cy + dy[j];
					int nx = cx + dx[j];
					if (ny >= 0 && nx >= 0 && ny < n && nx < n && visit[ny][nx] == 0) {
						visit[ny][nx] = 1;
						q.push(make_pair(ny, nx));
					}
				}
			}
			cnt++;
		}
	}

	return 0;
}