메모리

시간

1264 KB

0 ms

Code

#include <cstdio>
#include <queue>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	int map[200][200] = {0,};
	int result;

	int r1,c1,r2,c2;
	scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
	queue <pair<int, int> > queue;
	
	int mov_r[6] = {-2, -2, 0, 0, 2, 2};
	int mov_c[6] = {-1, 1, -2, 2, -1, 1};
	queue.push(make_pair(r1,c1));
	while (!queue.empty())
	{
		result = 0;
		for (int i = 0; i < 6; i++)
		{
			int rr = queue.front().first + mov_r[i];
			int cc = queue.front().second + mov_c[i];
			if(rr >= 0 && rr < n && cc >= 0 && cc < n)
			{
				if (map[rr][cc])
					continue ;
				map[rr][cc] = map[queue.front().first][queue.front().second] + 1;
				if (rr == r2 && cc == c2)
				{
					printf("%d", map[rr][cc]);
					return 0;
				}
				queue.push(make_pair(rr,cc));
			}
		}
		queue.pop();
	}
	printf("%d", -1);
	return 0;
}

문제 풀이

체스판에서 r, c 가 이동할 수 있는 경우는 총 6가지가 있다.

mov_r , mov_c 배열을 사용하여 인덱스를 움직여주고 queue<pair> 를 사용해서 방문한 인덱스 체크와 counting 을 함께 해주었다.

만약 움직일 수 있는 다음칸이 체스판 내에 있다면 방문여부를 체크 후 움직인 칸에 count + 1 을 헤주고

만약 도달해야할 칸에 도달 했다면 해당 값 출력을 한다.

만약 다음 방문할 칸이 체스판 범위를 넘어가면 continue , 큐에 넣지 않고 다음 칸을 체크한다.

큐에 값이 비었다면 해당 칸에 갈 수 없음으로 -1 출력을 한다.