7562번: 나이트 (BOJ C/C++)

7562번: 나이트

사용 언어: C++

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

풀이

그냥 BFS 문제인데 말의 이동 성향에 따라 dx와 dy를 조금 다르게 설정만 하면 된다!

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

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

int board[300][300];
int T, I, curx, cury, desx, desy;
queue<pair<int, int>> Q;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;
	while(T--)
	{
		cin >> I >> curx >> cury >> desx >> desy;
		for(int i=0; i<I; i++)
			fill(board[i], board[i]+I, -1); //초기화
		Q.push({curx, cury});
		board[curx][cury] = 0;
		while(!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			for(int dir=0; dir<8; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if(nx<0 || nx>=I || ny<0 || ny>=I) continue;
				if(board[nx][ny]>=0) continue;
				board[nx][ny] = board[cur.X][cur.Y] + 1;
				Q.push({nx, ny});
			}
		}
		cout << board[desx][desy] << '\n';
	}
	
	return 0;
}