[백준] 16948번 데스 나이트

문제: 16948번: 데스 나이트

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> board;
vector<vector<int>> visits;

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

int n;
int r1, c1, r2, c2;
vector<vector<int>> path;
void BFS() {
    queue<pair<int, int>> nexts;
    visits[r1][c1] = 1;
    nexts.push({ r1, c1 });

    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();

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

            if (nx <0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
            if (visits[nx][ny] == 1) continue;

            visits[nx][ny] = 1;
            nexts.push({ nx, ny });
            path[nx][ny] = path[cur.first][cur.second] + 1;
        }
    }
}

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

    cin >> n;
    board = vector<vector<int>>(n, vector<int>(n));
    visits = vector<vector<int>>(n, vector<int>(n));
    path = vector<vector<int>>(n, vector<int>(n));
 
    cin >> r1 >> c1 >> r2 >> c2;
    BFS();
    if (path[r2][c2] == 0) cout << -1;
    else
        cout << path[r2][c2];

    return 0;
}