[BOJ] 1261번 알고스팟 -deque

#include < iostream>
#include < deque>

using namespace std;

int dis[101][101];
bool check[101][101];
int board[101][101];

int dy[4] = {-1,0,1,0};
int dx[4] = {0,-1,0,1};

int n,m;

void bfs(int y,int x){
    deque<pair< int,int>> q;
    q.push_front(make_pair(y,x));

    check[y][x] = true;
    dis[y][x] = 0;

    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop_front();

        for(int dir=0;dir<4;dir++){
            int ny = y + dy[dir];
            int nx = x + dx[dir];

            if(ny<0 || nx<0 || ny>=n || nx>=m)
                continue;

            if(check[ny][nx] == false){
                check[ny][nx] = true;
                if(board[ny][nx] == 0){
                    q.push_front(make_pair(ny,nx));
                    dis[ny][nx] = dis[y][x];
                }else{
                    q.push_back(make_pair(ny,nx));
                    dis[ny][nx] = dis[y][x] + 1;
                }

            }

        }
    }

}

int main()
{
    cin>>m>>n;

    for(int i=0;i<n;i++){
        string temp;
        cin>>temp;
        for(int j=0;j<m;j++){
            if(temp[j] == '1')
                board[i][j] = 1;
            else
                board[i][j] = 0;
        }
    }

   /* for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }*/

    bfs(0,0);

   cout<<dis[n-1][m-1]<<endl;



    return 0;
}

https://www.acmicpc.net/problem/1261

1261번: 알고스팟