백준 16948번 데스 나이트

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

#include<iostream>
#include <string>
#include<queue>
#include <vector>

using namespace std;

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

bool visit[200][200];
int r1, r2, c1, c2;

struct Node
{
	int first;
	int second;
	int cost;
};
int main(void)
{
	int N;
	cin >> N;
	cin >> r1 >> c1 >> r2 >> c2;

	visit[r1][c1] = true;
	queue<Node> que;
	que.push({ r1,c1 });

	while (!que.empty())
	{
		int y = que.front().first;
		int x = que.front().second;
		int cost = que.front().cost;
		que.pop();

		if (y == r2 && x == c2)
		{
			cout << cost << endl;
			return 0;
		}

		for (int i = 0; i < 6; i++)
		{
			int newy = y + dy[i];
			int newx = x + dx[i];

			if (newy >= 0 && newy < N && newx >= 0 && newx < N)
			{
				if (!visit[newy][newx])
				{
					visit[newy][newx] = true;
					que.push({ newy,newx,cost + 1 });
				}
			}
		}
	}
	cout << -1 << endl;
}