BOJ 2178 미로 탐색

개요

BOJ 2178 미로 탐색
C++

#include <bits/stdc++.h>
using namespace std;

int N, M;
bool A[101][101] = {};
int visited[101][101] = {};
int x, y;

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

void bfs() {
    queue<pair<int,int>> q;
    q.push({1, 1});
    visited[1][1] = 1;
    int nx, ny;
    while(!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(ny>=1 && ny<=N && nx>=1 && nx<=M && A[ny][nx] && visited[ny][nx] == 0) {
                q.push({ny, nx});
                visited[ny][nx] = visited[y][x]+1;
            }
        }
    }
}

int main() {
    cin >> N >> M;
    string temp;
    for(y=1; y<=N; y++) {
        cin >> temp;
        for(x=1; x<=M; x++) {
            A[y][x] = temp[x-1] - '0';
        }
	}
    bfs();
    cout << visited[N][M];
}