[C++/2178] 미로 탐색 - using BFS

BOJ 2178

2178번: 미로 탐색

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int N, M;
// 동 서 남 북
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void BFS(vector<vector<int>> &v, vector<vector<bool>> &visited, int i, int j)
{
    queue<pair<int, int>> q;
    
    q.push({i, j});
    visited[i][j] = true;

    while(q.empty() == false)
    {
        auto temp = q.front();
        q.pop();
        
        for(int k = 0;k < 4;k++)
        {
            int tempR = temp.first + dx[k];
            int tempC = temp.second + dy[k];
            
            if (tempR < 0 || tempC < 0 || tempR >= N || tempC >= M)
                continue;
            else
            {
                if (visited[tempR][tempC] == false && v[tempR][tempC] == 1)
                {
                    visited[tempR][tempC] = true;
                    v[tempR][tempC] = v[temp.first][temp.second] + 1;
                    q.push({tempR, tempC});
                }
            }
        }
    }
}

int main(void)
{
    cin>>N>>M;
    
    vector<vector<int>> v(N, vector<int>(M, 0));
    vector<vector<bool>> visited(N, vector<bool>(M, false));
  
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            scanf("%1d", &v[i][j]);
        }
    }
    
    BFS(v, visited, 0, 0);
    cout<<v[N - 1][M - 1];
    
    return 0;
}