나이트의 이동

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	52423	27213	20242	50.811%

문제

체스판 위에 한 나이트가 놓여져 있다.

나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다.

나이트가 이동하려고 하는 칸이 주어진다.

나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다.

첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다.

체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다.

둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

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

예제 입력 1

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

예제 출력 1

11

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: sait2000
• 문제의 오타를 찾은 사람: sgchoi5

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

통과된 코드

#include <iostream>
#include <queue>

using namespace std;

constexpr int MAX = 300;

int _T, _I, _Res = 0;
int _DxDy[8][2] = { {-2,-1},{-2,1}, {2, 1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2} };
bool _IsVisted[MAX][MAX];
pair<int, int> Pos[2];

struct CntPos
{
	int _Cnt = 0;
	pair<int, int> _CntPos = {0, 0};

	CntPos(int _cnt, pair<int, int> _cntPos) : _Cnt(_cnt), _CntPos(_cntPos) {};
};

queue<CntPos> BFSQueue;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> _T;
	while (_T--)
	{
		cin >> _I;
		for (int i = 0; i < _I; i++)
			for (int j = 0; j < _I; j++)
				_IsVisted[i][j] = false;
			
		int _x, _y;
		for (int i = 0; i < 2; i++) {
			cin >> _x >> _y;
			Pos[i].first = _x;
			Pos[i].second = _y;
		}

		while (!BFSQueue.empty())
			BFSQueue.pop();
		
		BFSQueue.push(CntPos(0, Pos[0]));
		_IsVisted[Pos[0].first][Pos[0].second] = true;
		while (!BFSQueue.empty()) {
			Pos[0] = BFSQueue.front()._CntPos;
			int _cnt = BFSQueue.front()._Cnt;
			BFSQueue.pop();
			if (Pos[0] == Pos[1]) {
				_Res = _cnt;
				break;
			}

			for (int i = 0; i < 8; i++) {
				int _dx = Pos[0].first + _DxDy[i][0];
				int _dy = Pos[0].second + _DxDy[i][1];
				if (_dx < 0 || _dy < 0 || _dx >= _I || _dy >= _I)
					continue;
				if (_IsVisted[_dx][_dy]) 
					continue;
				BFSQueue.push(CntPos(_cnt + 1, { _dx, _dy }));
				_IsVisted[_dx][_dy] = true;
			}
		}

		cout <<_Res << "\n";
	}

	return 0;
}