백준-나이트의 이동.cpp.txt

#include<iostream>
#include <queue>
#include <cstdio>
#include<algorithm>
#include<utility>

using namespace std;
int N;
int arr[301][301];
bool visit[301][301];
int depth[301][301];
int *sol;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T, ex_T;
	cin >> T;
	sol = new int[T];
	ex_T = T;
	while (T != 0)
	{
		cin >> N;
		int Nx, Ny, Dx, Dy;
		cin >> Nx >> Ny;

		cin >> Dx >> Dy;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				arr[i][j] = 0;
				visit[i][j] = false;
				depth[i][j] = 0;
			}
		}

		arr[Nx][Ny] = 1;
		arr[Dx][Dy] = 2;

		queue<pair<int, int>> q;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] == 1)
				{
					q.push(make_pair(i, j));
					visit[i][j] = false;
				}

			}
		}
		bool check = true;
		while (!q.empty())
		{
			Nx = q.front().first;
			Ny = q.front().second;
			q.pop();

			if (Nx + 2 < N&&Ny + 1<N&&visit[Nx + 2][Ny + 1] == false)
			{
				if (arr[Nx + 2][Ny + 1] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx + 2][Ny + 1] = true;
				depth[Nx + 2][Ny + 1] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx + 2, Ny + 1));
			}
			if (Nx + 1 < N&&Ny + 2<N&&visit[Nx + 1][Ny + 2] == false)
			{
				if (arr[Nx + 1][Ny + 2] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx + 1][Ny + 2] = true;
				depth[Nx + 1][Ny + 2] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx + 1, Ny + 2));
			}
			if (Nx + 2 < N&&Ny - 1 >= 0 && visit[Nx + 2][Ny - 1] == false)
			{
				if (arr[Nx + 2][Ny - 1] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx + 2][Ny - 1] = true;
				depth[Nx + 2][Ny - 1] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx + 2, Ny - 1));
			}
			if (Nx + 1 < N&&Ny - 2 >= 0 && visit[Nx + 1][Ny - 2] == false)
			{
				if (arr[Nx + 1][Ny - 2] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx + 1][Ny - 2] = true;
				depth[Nx + 1][Ny - 2] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx + 1, Ny - 2));
			}
			if (Nx - 2 >= 0 && Ny + 1<N&&visit[Nx - 2][Ny + 1] == false)
			{
				if (arr[Nx - 2][Ny + 1] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx - 2][Ny + 1] = true;
				depth[Nx - 2][Ny + 1] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx - 2, Ny + 1));
			}
			if (Nx - 1 >= 0 && Ny + 2<N&&visit[Nx - 1][Ny + 2] == false)
			{
				if (arr[Nx - 1][Ny + 2] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx - 1][Ny + 2] = true;
				depth[Nx - 1][Ny + 2] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx - 1, Ny + 2));
			}
			if (Nx - 2 >= 0 && Ny - 1 >= 0 && visit[Nx - 2][Ny - 1] == false)
			{
				if (arr[Nx - 2][Ny - 1] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx - 2][Ny - 1] = true;
				depth[Nx - 2][Ny - 1] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx - 2, Ny - 1));
			}
			if (Nx - 1 >= 0 && Ny - 2 >= 0 && visit[Nx - 1][Ny - 2] == false)
			{
				if (arr[Nx - 1][Ny - 2] == 2)
				{
					sol[T] = depth[Nx][Ny] + 1;
					check = false;
					break;
				}
				visit[Nx - 1][Ny - 2] = true;
				depth[Nx - 1][Ny - 2] = depth[Nx][Ny] + 1;
				q.push(make_pair(Nx - 1, Ny - 2));
			}

		}
		if(check)
		sol[T] = 0;
		else
		{
			;
		}

		T--;
	}
	
	for (int i = ex_T; i > 0; i--)
	{
		cout << sol[i] << endl;
	}
	return 0;
}