[BOJ] 2178번: 미로 탐색

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

4방향으로 BFS를 돌면 된다.

#include <cstdio>
#include <queue>
using namespace std;

const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int n, m;
char a[102][102];
int vst[102][102];

struct ED
{
    int x, y;
    ED(int x, int y) : x(x), y(y) {}
};

int BFS(int x, int y)
{
    queue<ED> q;
    q.push(ED(x, y));
    vst[x][y] = 1;

    while (!q.empty())
    {
        int xx = q.front().x, yy = q.front().y;
        q.pop();

        if (xx == n - 1 && yy == m - 1)
            break;

        for (int i = 0; i < 4; ++i)
        {
            int nx = xx + dx[i], ny = yy + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m && !vst[nx][ny] && a[nx][ny] == '1')
            {
                q.push(ED(nx, ny));
                vst[nx][ny] = vst[xx][yy] + 1;
            }
        }
    }

    return vst[n - 1][m - 1];
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%s", a[i]);
    printf("%d\n", BFS(0, 0));
    return 0;
}