[C++] 백준 14442 - 벽 부수고 이동하기 2

14442번: 벽 부수고 이동하기 2

---

풀이

이전에 했던 1600 말이 되고픈 원숭이랑 비슷하게 풀었다.

남은 벽부수기 횟수에따른 flag를 배열을 만들고 남은거리를 저장했다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

int board[1001][1001];
int flag[1001][1001][11];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int w,h,k;
int answer = 10000000;

bool InMap(int x,int y){
    if(0 <= x && x < w && 0<= y && y < h)
    return true;
    return false;
}
void bfs(){
    // x y 벽횟수 이동거리
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(0,0), make_pair(k,1)));
    
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int c = q.front().second.first;
        int l = q.front().second.second;
        q.pop();
        if(!InMap(x,y))
        continue;
        
        if(board[y][x] == 1 && c <= 0){
            continue;
        }
        if(board[y][x] == 1 && c > 0){
            c--;
        }
        
        if(flag[y][x][c] != 0 && flag[y][x][c] <= l)
        continue;
        
        if(answer <= l)
        continue;
        
        if(x == w-1 && y == h-1){
            answer = min(answer, l);
            flag[y][x][c] = answer;
            continue;
        }
        flag[y][x][c] = l;
        
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            q.push(make_pair(make_pair(nx,ny), make_pair(c,l+1)));
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> h >> w >> k;
    string s;
    for(int y = 0; y < h; y++){
            cin >> s;
        for(int i =0; i < s.length(); i++){
            board[y][i] = ((int)s[i] - (int)'0');
        }
    }
    bfs();
    if(answer != 10000000)
    cout << answer;
    else{
        cout << -1;
    }
    return 0;
}