백준 7562 // 최단거리는 bfs, 핵심로직공부

7562번: 나이트의 이동 (acmicpc.net)

7562번: 나이트의 이동

*최단거리 bfs 핵심로직

1. 방문배열 값 == 이동거리

1-1. 초기 방문배열값=1

2. while-for문내 : v[ny][nx] = v[y][x] + 1;

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int l, tc,ny,nx,o1,o2,t1,t2,y,x,ret,  a[304][304], v[304][304];
int dx[] = {1,2,2,1,-1,-2,-2,-1};
int dy[] = {-2,-1,1,2,2,1,-1,-2};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cin >> tc;
    for (int i = 0; i < tc;++i)
    {
        ret = 0;
        cin >> l;
        cin >> o1 >> o2>>t1>>t2;
        if (o1 == t1 && o2 == t2) { cout << 0 << "\n"; continue; };
        fill(&v[0][0], &v[0][0]+ 304 * 304, 0);
        fill(&a[0][0], &a[0][0]+ 304 * 304, 0);

        queue<pair<int, int>> q;
        q.push({ o1, o2 });
        v[o1][o2] = 1;

        while (q.size())
        {
            tie(y, x) = q.front(); q.pop();
            for (int i = 0; i < 8; ++i)
            {
                ny = y + dy[i];
                nx = x + dx[i];
                if (ny >= l || nx >= l || nx < 0 || ny < 0) continue;
                if (v[ny][nx]) continue;
                
                q.push({ ny,nx });
                v[ny][nx] = v[y][x] + 1;
                if (ny == t1 && nx == t2)
                {
                    cout << v[ny][nx]-1 << "\n"; continue;
                };

                
            }
        }

    }
    

    return 0;
}