백준 16948 c++ 데스 나이트

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

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 <queue>
using namespace std;

int N;
int r1, c1, r2, c2;
int visit[200][200];
int dx[] = { -2,-2,0,0,2,2 };
int dy[] = { -1,1,-2,2,-1,1 };
bool found;

void bfs()
{
	queue<pair<int, int>>q;
	q.push(make_pair(r1, c1));

	while (!q.empty())
	{
		int nowR = q.front().first;
		int nowC = q.front().second;
		q.pop();
		int count = visit[nowR][nowC] + 1;

		for (int i = 0; i < 6; i++)
		{
			int nextR = nowR + dx[i];
			int nextC = nowC + dy[i];
			if ((nextR < 0 || nextR >= N) || (nextC < 0 || nextC >= N))//범위 밖이면 스킵
				continue;
			if (visit[nextR][nextC] != 0)//이미 차있으면
				continue;
			if (nextR == r2 && nextC == c2)//다음이 답이면?
			{
				found = true;
				visit[r2][c2] = count;
				return;
			}
			visit[nextR][nextC] = count;
			q.push(make_pair(nextR, nextC));
		}
	}
	return;
}

int main()
{
	cin >> N;
	cin >> r1 >> c1 >> r2 >> c2;
	bfs();
	if (found == true)
		cout << visit[r2][c2];
	else
		cout << -1;
}