백준 16509 - 장군(C++)

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

16509번: 장군

특이한 8방향 그래프 이동을 통해 원하는 목적지에 도달할 수 있는지를 구하는 문제입니다.

상이 왕을 잡을 수 있는 횟수가 얼마인지를 구하는 문제입니다.

상이 이동할 수 있는 8방향을 통해 계속 이동하면서 왕이 있는 곳까지 움직이면 되는 문제입니다.

주의할 점은 상이 이동하는 길에 다른 말이 있을 경우 해당 방향으로 움직일 수 없다는 것입니다.

해당 조건만 주의하면 쉽게 풀 수 있는 문제입니다.

 

 

 

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

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

using namespace std;

P start, finish;
int check[10][10];
int dx[8] = {-3, -3, -2, -2, 2, 2, 3, 3};
int dy[8] = {-2, 2, -3, 3, -3, 3, -2, 2};

int Dx[8][2] = {
                    {-1, -2},
                    {-1, -2},
                    {0, -1},
                    {0, -1},
                    {0, 1},
                    {0, 1},
                    {1, 2},
                    {1, 2}
                };
int Dy[8][2] = {
                    {0, -1},
                    {0, 1},
                    {-1, -2},
                    {1, 2},
                    {-1, -2},
                    {1, 2},
                    {0, -1},
                    {0, 1}
                };

bool can_go(int x, int y, int way){
    for(int i = 0; i < 2; i++){
        int xx = x + Dx[way][i];
        int yy = y + Dy[way][i];
        if(xx == finish.F && yy == finish.S) return false;
    }
    return true;
}

int bfs(){
    queue<PP> q;
    q.push({start, 0});
    check[start.F][start.S] = 1;
    while(!q.empty()){
        int x = q.front().F.F;
        int y = q.front().F.S;
        int cnt  = q.front().S;
        q.pop();
        if(x == finish.F && y == finish.S) return cnt;
        for(int i = 0; i < 8; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(!can_go(x,y,i)) continue;
            if(xx >= 0 && xx <= 9 && yy >= 0 && yy <= 8){
                if(check[xx][yy] == 0){
                    check[xx][yy] = 1;
                    q.push({{xx,yy}, cnt+1});
                }
            }
        }
    }
    return -1;
}

void solve(){
   int ans = bfs();
   cout << ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> start.F >> start.S;
    cin >> finish.F >> finish.S;
    solve();
    return 0;
}

 

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