[백준 1261] 알고스팟 (BFS) (C/C++) (★★)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int crash;    
}node;
 
int row, col;
int map[110][110];
int visited[110][110][210];
queue<node> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y, int crash)
{
    q.push({x, y, crash});
    visited[x][y][crash] = 1;
    
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        crash = q.front().crash;
        q.pop();
        
        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] == 0 && visited[xpos][ypos][crash] == 0 && crash <= row+col-3)
            {
                q.push({xpos, ypos, crash});
                visited[xpos][ypos][crash] = 1;
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos][crash+1] == 0 && crash+1 <= row+col-3)
            {
                q.push({xpos, ypos, crash+1});
                visited[xpos][ypos][crash+1] = 1;    
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1261_input.txt", "r", stdin);
 
    cin >> col >> row;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS(0, 0, 0);
    
    for(int i = 0; i <= row+col-3; i++)
    {
        if(visited[row-1][col-1][i] == 1)
        {
            cout << i;
            break;
        }
    }
    
    return 0;
}