2665번: 미로만들기

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


$O(n^2)$

#include<cstdio>
#include<string.h>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int n, ck[50][50], t;
char c[50][51];
void f(int x, int y) {
    if (x<0 || y<0 || x >= n || y >= n || ck[x][y])return;
    ck[x][y] = 1;
    if (c[x][y] == '0') { c[x][y]++; return; }
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%s", c[i]);
    for (; !ck[n - 1][n - 1]; t++) memset(ck, 0, sizeof(ck)), f(0, 0);
    printf("%d", t - 1);
    return 0;
}