2178번: 미로 탐색

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


$O(nm)$

#include<cstdio>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int qx[100 * 100], qy[100 * 100], h, t;
int n, m, c[100][100], r[100][100] = { 1 };
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%1d", &c[i][j]);
    qx[t] = 0; qy[t++] = 0;
    while (h^t) {
        for (int i = 0; i < 4; i++) {
            int tx = qx[h] + fx[i], ty = qy[h] + fy[i];
            if (tx<0 || ty<0 || tx >= n || ty >= m || !c[tx][ty]) continue;
            c[tx][ty] = 0;
            r[tx][ty] = r[qx[h]][qy[h]] + 1;
            qx[t] = tx; qy[t++] = ty;
        }
        h++;
    }
    printf("%d", r[n - 1][m - 1]);
    return 0;
}