백준 18404 - 현명한 나이트(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18404

18404번: 현명한 나이트

BFS를 이용해 푸는 문제입니다.

일반적인 상하좌우 4방향 탐색이 아닌, 나이트 이동인 8방향으로 탐색하는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define INF 987654321
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
int map[501][501];
int check[501][501];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
P start;
vector<P> knight;

void bfs(){
    queue<P> q;
    check[start.F][start.S] = 1;
    q.push(start);
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 8; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){
                if(check[xx][yy] == 0){
                    check[xx][yy] = check[x][y] + 1;
                    q.push({xx, yy});
                }
            }
        }
    }
}

void solve(){
    bfs();
    for(int i = 0; i < M; i++){
        cout << check[knight[i].F][knight[i].S] - 1 << " ";
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    cin >> start.F >> start.S;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        knight.push_back({x, y});
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요