7562 나이트의 이동

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

7562번: 나이트의 이동

 

<개인 풀이>

1. 시작점부터 끝점까지 BFS 탐색

 

2. BFS 탐색이 끝나면, 도착지점의 거리 값을 불러온다.

 

3. 테스트케이스 수 만큼 반복.

 

#include<stdio.h>
#include<queue>
#include<cstring>
int check[300][300];

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

using namespace std;
int size; //체스판 크기 

int sx, sy; //start x,y 
int ex, ey; //end x,y
int bfs(int x, int y, int cnt);
int main(void)
{
	int n = 0; //테스트 케이스수

	scanf("%d", &n);
	
	while (n--)
	{
		scanf("%d", &size);
		scanf("%d %d", &sx, &sy);
		scanf("%d %d", &ex, &ey);

		int ans=bfs(sx, sy,1);
		printf("%d\n", ans);
		memset(check, 0, sizeof(check));
	}

	return 0;
}

int bfs(int x, int y, int cnt)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	check[x][y] = cnt;
	if (x == ex && y == ey)
	{
		return check[x][y] - 1;
	}
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (unsigned short i = 0; i < 8; ++i)
		{
			int xn = x + dx[i];
			int yn = y + dy[i];

			if (xn >= 0 && xn < size && yn >= 0 && yn < size&&
				check[xn][yn] == 0)
			{

				check[xn][yn] = check[x][y] + 1;

				if (xn == ex&&yn == ey)
				{
					return check[xn][yn] - 1;
				}
				q.push(make_pair(xn, yn));
			}
		}

	}
}