[C++] 백준 1600 - 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

---

풀이

남은 나이트 이동 횟수에 따라 이동거리를 저장하는 배열을 만들어서 bfs로 풀었다

 

 

 

코드

#include <bits/stdc++.h>

using namespace std;

int dhx[8] = {-2,-1,1,2,-2,-1,1,2};
int dhy[8] = {1,2,2,1,-1,-2,-2,-1};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int board[201][201];

int flag[201][201][31];
int answer = 10000000;
int k,w,h;

bool InMap(int x,int y){
    if(0 <= x && x < w && 0 <= y && y < h)
    return true;
    return false;
}

void bfs(){
    queue<pair<pair<int,int>,pair<int,int>>> q;
    // x,y 이동횟수, 남은 말이동
    q.push(make_pair(make_pair(0,0),make_pair(1,k)));
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int c = q.front().second.first;
        int m = q.front().second.second;
        
        q.pop();
        if(!InMap(x,y))
        continue;
        
        if(board[y][x] == 1){
            continue;
        }
        if(flag[y][x][m] != 0 && flag[y][x][m] <= c){
            continue;
        }
        
        if(answer <= c){
            continue;
        }
        flag[y][x][m] = c;
        if(x==w-1 && y==h-1){
            answer = min(answer, c);
            continue;
        }
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            q.push(make_pair(make_pair(nx,ny),make_pair(c+1,m)));
        }
        
        if(m > 0){
           for(int i = 0; i < 8; i++){
            int nx = x + dhx[i];
            int ny = y + dhy[i];
            q.push(make_pair(make_pair(nx,ny),make_pair(c+1,m-1)));
        } 
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> k >> w >> h;
    
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            cin>> board[y][x];
        }
    }
    bfs();
    if(answer != 10000000)
    cout << answer-1;
    else
    cout << -1;
    return 0;
}