vijos-1057.cpp

/*
    Luna Capsule / vijos-1057
 
    Problem: https://vijos.org/p/1057
    Record: https://vijos.org/records/53ff29a048c5fc314f8b4571
    
    - 一道很水的DP题, 方程f[i][j] = min(f[i - 1][j - 1], f[i][j - 1], f[i - 1][j])
      自行设计复杂一点的数据手工模拟一下DP过程就可以得到方程
*/
 
#include <cstdio>
 
const unsigned VERTEX_MAX = 1001;
 
inline unsigned min(unsigned a, unsigned b) { return (a < b) ? a : b; }
 
unsigned n, m, f[VERTEX_MAX][VERTEX_MAX];
 
int main() {
    unsigned i, j, ans = 0;
    unsigned a; // 这是个坑千万不要用bool来图省事...
 
    scanf("%d %d", &n, &m);
    for (i = 0; i <= n; i++)
        f[i][0] = 0;
    for (j = 0; j <= m; j++)
        f[0][j] = 0;
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%d", &a);
            if (a == 1)
                f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;
            else
                f[i][j] = 0;
            //printf("[%d,%d] ", a, f[i][j]);
            if (f[i][j] > ans)
                ans = f[i][j];
        }
        //printf("\n");
    }
 
    printf("%d", ans);
}