题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
输入格式
输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.
输出格式
一个整数，最大正方形的边长
输入输出样例
输入 #1
4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1
输出 #1
2
思路
令 f [ i ] [ j ] 为第 a [ i ] [ j ] 个格子上的最大正方形边长。
显然当 a [ i ] [ j ] == 1 时，状态可能发生变化，转移 f [ i ] [ j ] 应该等于上、左上、左的格子能取到的最小值 + 1 。
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
namespace _buff {
const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, 1, BUFF, stdin);
}
return ib == ie ? -1 : *ib++;
}
}
int qread() {
using namespace _buff;
int ret = 0;
bool pos = true;
char c = getc();
for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '0' && c <= '9'; c = getc()) {
ret = (ret << 3) + (ret << 1) + (c ^ 48);
}
return pos ? ret : -ret;
}
const int maxn = 107;
int n, m;
int a[maxn][maxn];
int f[maxn][maxn];
int main()
{
read(n);
read(m);
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
read(a[i][j]);
}
}
int ans = INT_MIN;
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
if(a[i][j]) {
f[i][j] = min(
f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])
) + 1;
}
ans = max(f[i][j], ans);
}
}
cout << ans << endl;
return 0;
}