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

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct data{int y,x,wall,cnt;}; //y,x,부신 벽,거리
queue<struct data> q;
int arr[1002][1002];
int copy_arr[1002][1002][11]; // y,x,부신 벽의 갯수
int n,m,kv,x,y,cnt,wall,ans=999999999;
int bfs(int tot){
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        wall=q.front().wall; // 현재까지 부신 벽의 갯수
        cnt=q.front().cnt; // 이동거리
 
        q.pop();
      
        if(y==n && x==m){
            if(cnt<ans)
                ans=cnt;
            return ans;
        }
 
        for(int k=0; k<4; k++){
            int nx=x+dx[k];
            int ny=y+dy[k];
 
            if(0<nx && nx<=m && 0<ny && ny<=n){
                // 빈 공간이고 아직 방문하지 않았다면
                if(arr[ny][nx]==0 && copy_arr[ny][nx][wall]==0){
                    q.push({ny,nx,wall,cnt+1});
                    copy_arr[ny][nx][wall]=1;
                }
 
                // 벽이지만 아직 부실 수 있는 벽의 갯수가 남아있으면 방문
                else if(wall>0 && copy_arr[ny][nx][wall]==0){
                    q.push({ny,nx,wall-1,cnt+1});
                    copy_arr[ny][nx][wall]=1;
 
                }
            }
        }
    }
    return -1;
}
int main(void){
    scanf("%d %d %d", &n, &m, &kv);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            scanf("%1d", &arr[i][j]);
    }
    
    q.push({1,1,kv,1});
    copy_arr[1][1][kv]=1;
    
 
    printf("%d", bfs(kv));
    
    return 0;
}