BOJ 7562 : 나이트의 이동

BOJ 7562

[BOJ 7562(S2) 리뷰]

 

난 그림만 나오면 쫄고 시작하는데 그리 어려운 문제는 아니다.

기존에 상,하,좌,우 4방향 탐색하던것을 8개의 방향에대해 탐색을 하면된다.

board배열에 길이를 저장하여 목적지의 길이가 몇인지 출력하면 된다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second

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

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)
			fill(board[i], board[i] + n, 0);
		pair<int, int> start;
		pair<int, int> dest;
		queue<pair<int, int>> Q;
		int temp[2];
		for (int i = 0; i < 2; i++)
			cin >> temp[i];
		start.X = temp[0]; start.Y = temp[1];
		for (int i = 0; i < 2; i++)
			cin >> temp[i];
		dest.X = temp[0]; dest.Y = temp[1];

		Q.push({ start.X, start.Y });
		board[start.X][start.Y] = 1;
		int cnt = 0;
		while (!Q.empty())
		{
			auto cur = Q.front();
			if (cur == dest) break;
			Q.pop(); cnt++;
			for (int dir = 0; dir < 8; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (board[nx][ny] != 0) continue;
				board[nx][ny] = board[cur.X][cur.Y]+1;
				Q.push({ nx,ny });

			}
		}
		cout << board[dest.X][dest.Y]-1 << '\n';
	}

}