벽 부수고 이동하기

#include<iostream>
#include<queue>
#include<utility>
 
 
using namespace std;
 
int r,c;
string map[1000];
int dist[1000][1000][2];
bool d[1000][1000][2];
int dx[] ={0,0,1,-1};
int dy[] = {1,-1,0,0};
 
void bfs(){
    queue<pair<pair<int,int>,int>> q;
    q.push({{0,0},0});
    d[0][0][0] = true;
    dist[0][0][0] = 1;
    while(!q.empty()){
        int x = q.front().first.first;int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx <0 || nx>= r|| ny<0 ||ny>=c) continue;
            if(d[nx][ny][cnt] == true) continue;
            if(map[nx][ny]== '0' ){
                d[nx][ny][cnt] = true;
                dist[nx][ny][cnt] = dist[x][y][cnt]+1;
                q.push({{nx,ny},cnt});
            }
            if(map[nx][ny] == '1' && cnt == 0){
                d[nx][ny][cnt] = true;
                dist[nx][ny][cnt+1] = dist[x][y][cnt]+1;
                q.push({{nx,ny},cnt+1});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin>>r>>c;
 
    for(int i = 0; i< r; i++){
        cin>>map[i];
    }
    bfs();
    int s = 0,z =0;
    if(dist[r-1][c-1][0] == 0)
        s = 987654321;
    else s = dist[r-1][c-1][0];
    if(dist[r-1][c-1][1] == 0)
        z = 987654321;
    else z = dist[r-1][c-1][1];
    if( s > z)
        s = z;
 
    
    if(s == 987654321)
        cout<<-1<<'\n';
    else
        cout<<s<<'\n';
    return 0;
}

DP냄새가 나는 BFS였다 

단 한번만 뚫을수있다는점을 생각하면 그다지어렵지는않은문제