[C++]백준 18404번 현명한 나이트

📌문제 링크

---

https://www.acmicpc.net/problem/18404

📌문제 설명

---

상대편말의 위치에서 bfs탐색을 시작해서 나이트위치까지의 최단거리를 찾아 기록한다

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> v;
int N, M, X, Y, mp[501][501];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

struct comp{
    int x, y, cnt;
};

void input(){
    cin >> N >> M >> X >> Y;
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

void init(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            mp[i][j] = -1;
        }
    }
}

void bfs(){
    queue<comp> q;
    q.push({X, Y, 0});
    mp[X][Y] = 0;
    while(!q.empty()){
        auto [x, y, cnt] = q.front();
        q.pop();
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx <= 0 || nx > N || ny <= 0 || ny > N || mp[nx][ny] != -1){
                continue;
            }
            mp[nx][ny] = cnt + 1;
            q.push({nx, ny, cnt + 1});
        }
    }
}

void solve(){
    input();
    init();
    bfs();
    for(auto it : v){
        cout << mp[it.first][it.second] << ' ';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}