[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int cnt;
}node;
 
int map[1010][1010];
int row, col, crash;
int Min = 99999999;
 
queue<node> q;
int visited[1010][1010][11];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 1 && x <= row && y >= 1 && y <= col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[1][1][0] = 1;
    q.push({1, 1, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
        
        if(x == row && y == col)
        {
            if(visited[row][col][cnt] < Min)
            {
                Min = visited[row][col][cnt];
            }
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos][cnt+1] == 0 && cnt+1 <= crash)
            {
                visited[xpos][ypos][cnt+1] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt+1});
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos][cnt] == 0 && cnt <= crash)
            {
                visited[xpos][ypos][cnt] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B14442_input.txt", "r", stdin);
    
    scanf("%d %d %d", &row, &col, &crash);
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS();
 
    if(Min == 99999999)
    {
        cout << -1;
    }
    else
    {
        cout << Min;
    }
        
    return 0;
}