문제풀이/백준
[C++] 백준 14442 - 벽 부수고 이동하기 2
레옹
2023. 10. 7. 18:48
풀이
이전에 했던 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;
}