[백준/C,C++] 7562번: 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

풀이

최단 거리를 찾는 문제이기 때문에 전형적인 BFS 문제라고 볼 수 있습니다.

 

가장 기본적인 2차원 배열 위에서 상하좌우로 이동 가능한 미로 문제 등과 달리

 

나이트가 이동 가능한 8방향으로 이동하며 탐색합니다.

 

 

역시나 depth를 계산해 주면 되는 문제고 특별히 어려운 점은 없습니다.

 

#include<iostream>
#include<queue>
#include<cstring>

#define py first
#define px second

using namespace std;

using PAIR = pair<int, int>;

const int MAX = 300;

int cnt[MAX][MAX];
queue<PAIR> q;
PAIR src, dst;
PAIR d[8] = {
    {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
    {1, 2}, {2, 1}, {2, -1}, {1, -2}
};


void search(int len)
{
    cnt[src.py][src.px] = 1;
    q.push(src);

    while (!q.empty()) {
        PAIR node = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int ny = node.py + d[i].py;
            int nx = node.px + d[i].px;
            if (ny >= 0 && nx >= 0 && ny < len && nx < len) {
                if (!cnt[ny][nx]) {
                    cnt[ny][nx] = cnt[node.py][node.px] + 1;
                    q.push(pair(ny, nx));
                }
            }
        }
    }
}

int main(void)
{
    int n; cin >> n;

    while (n--) {
        int l; cin >> l;
        cin >> src.py >> src.px;
        cin >> dst.py >> dst.px;

        memset(cnt, 0, sizeof(cnt));

        search(l);

        cout << cnt[dst.py][dst.px] - 1 << '\n';
    }

    return 0;
}

반례

Input

3
8
0 0
7 7
15
5 5
6 6
300
0 0
299 299

Output

6

2

200