[C++] 백준 문제풀이 (BFS) 2178번 미로탐색

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

2178번: 미로 탐색

 

#include <bits/stdc++.h>

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m;
std::string map[100];
int dist[100][100];

void move() {
    std::queue<std::pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 1;

    while(!q.empty()){
        auto [y, x] = q.front(); q.pop();
        if (y == n - 1 && x == m - 1) break;
        for (int dir = 0; dir < 4; ++dir){
            int ny = y + dy[dir], nx = x + dx[dir];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (dist[ny][nx] != 0 || map[ny][nx] == '0') continue;
            q.push({ny, nx});
            dist[ny][nx] = dist[y][x] + 1;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;

    for (int i = 0; i < n; ++i){
        std::cin >> map[i];
    }
    move();
    std::cout << dist[n - 1][m - 1] << "\n";
    return 0;
}