2636번: 치즈

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


$O(n^3)$

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

$O(n^2)$

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, m, c[MXN + 2][MXN + 2], ck[MXN + 2][MXN + 2], t, r;
queue<pair<int, int> > q;
void f(int x, int y, int z) {
    if (c[x][y]) if (z > t) t = z, r = 1; else if (z == t)r++;
    ck[x][y] = z;
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx<0 || ty<0 || tx>n + 1 || ty>m + 1 || ck[tx][ty]) continue;
        c[tx][ty] ? ck[tx][ty] = z + 1, q.push({ tx,ty }) : f(tx, ty, z);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &c[i][j]);
    f(0, 0, 1);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        f(x, y, ck[x][y]);
        q.pop();
    }
    printf("%d\n%d", t - 1, r);
    return 0;
}