나이트의 이동 7562

문제

접근 방법

나이트가 이동할 수 있는 범위는 8방향이다. 2와 1을 음수, 양수로 조합한 8개이므로 해당 방향으로 탐색하면 된다. 칸을 이동할 때마다 몇 번 만에 도착했는지 남기고 값이 있는 곳은 다시 가지 않게끔 해주면 된다.

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[] = {2, 2, 1, 1, -1, -1, -2, -2}, dy[] = {1, -1, 2, -2, 2, -2, 1, -1};
int map[301][301];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    queue<pair<int, int>> bfs;
    while (T--)
    {
        memset(map, 0, sizeof(map));
        bfs = queue<pair<int, int>>();
        int l;
        cin >> l;
        int startX, startY, endX, endY;
        cin >> startX >> startY >> endX >> endY;
        bfs.push({startX, startY});
        while (!bfs.empty())
        {
            auto cur = bfs.front();
            if (cur.first == endX && cur.second == endY)
                break;
            bfs.pop();
            for (int i = 0; i < 8; ++i)
            {
                pair<int, int> next = {cur.first + dx[i], cur.second + dy[i]};
                if (next.first < 0 || next.second < 0 || next.first >= l || next.second >= l)
                    continue;
                if (map[next.first][next.second])
                    continue;
                map[next.first][next.second] = map[cur.first][cur.second] + 1;
                bfs.push(next);
            }
        }
        cout << map[bfs.front().first][bfs.front().second] << "\n";
    }
    return 0;
}

풀이

4방향 BFS를 8방향 BFS로 사용할 수 있는지에 대한 문제라고 생각한다. 8방향으로 진행해주면 된다.