7562번 나이트의 이동

문제:

• 문제 링크

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

입력:

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

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

출력:

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

접근 방법

1. 출발지를 큐에 삽입
2. 나이트가 이동할 수 있는 칸에 전부 BFS
3. 도착지에 도착하면 종료코드

접기/펼치기

#include <iostream>
#include <queue>
using namespace std;

int map[301][301] = {};

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;

    cin >> t;

    while (t--)
    {
        int n;
        int tmp1, tmp2;

        queue<pair<int, int>> q;
        int count = 0;
        cin >> n >> tmp1 >> tmp2;
        q.push(make_pair(tmp1, tmp2));
        cin >> tmp1 >> tmp2;
        pair<int, int> end = {tmp1, tmp2};

        for (int i = 0; i < n; i++)
            fill_n(map[i], n, 0);
        bool find = false;
        while (!q.empty())
        {
            int len = q.size();

            for (int z = 0; z < len; z++)
            {
                pair<int, int> cur = q.front();
                q.pop();
                if (cur.first == end.first && cur.second == end.second)
                {
                    find = true;
                    break;
                }

                for (int i = 0; i < 8; i++)
                {
                    int nx = cur.first + dx[i];
                    int ny = cur.second + dy[i];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                        continue;

                    if (map[nx][ny] == 0)
                    {
                        q.push(make_pair(nx, ny));
                        map[nx][ny] = 1;
                    }
                }
            }
            if (find)
            {
                cout << count << "\n";
                break;
            }
            count++;
        }
    }
}