백준 7562 - 나이트의 이동

www.acmicpc.net/problem/7562

 

각 테스트 케이스마다 bfs를 수행하여 나이트의 최소 이동 횟수를 찾으면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int t;
int n;
int a, b, c, d;
int cnt;
bool vst[300][300];
int nxt[8][2]
{
    {1, 2},
    {1, -2},
    {2, 1},
    {2, -1},
    {-1, 2},
    {-1, -2},
    {-2, 1},
    {-2, -1}
};
 
void bfs(int x, int y);
inline int mtdist(int a, int b, int c, int d) { return abs(a - c) + abs(d - b); }
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> t;
 
    while (t--)
    {
        memset(vst, 0, sizeof vst);
        cnt = 1e9;
        cin >> n >> a >> b >> c >> d;
        vst[a][b] = 1;
        bfs(a, b);
 
        cout << cnt << '\n';
    }
}
 
void bfs(int x, int y)
{
    queue<vector<int>> q;
    q.push({x, y, 0});
 
    while (q.size())
    {
        auto cur = q.front();
        q.pop();
 
        if (cur[0] == c && cur[1] == d)
        {
            cnt = min(cnt, cur[2]);
            return;
        }
 
        for (int i = 0; i < 8; ++i)
        {
            int nx = cur[0] + nxt[i][0], ny = cur[1] + nxt[i][1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || vst[nx][ny])
                continue;
 
            vst[nx][ny] = 1;
            q.push({nx, ny, cur[2] + 1});
        }
    }
}