贞白铁战逸 @ 2018-09-11 23:26:53
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[2505][2505], v[2505][2505], u[2505][2505], maxx = 0;
int n, m;
struct node
{
int up, left, right;
}f[2505][2505];
int main()
{
int i, j, k = 0, l;
cin >> n >> m;
for (i = 1; i<= n; i++)
{
for (j = 1; j<= m; j++)
{
scanf("%d", &a[i][j]);
if (!a[i][j])
{
if (i + 1 <= n) f[i + 1][j].up = f[i][j].up + 1;
if (j + 1 <= m) f[i][j + 1].left = f[i][j].left + 1;
}
else
{
l = j;
v[i][j] = 1;
u[i][j] = 1;
}
f[i][l].right = j - l;
}
for (j = l - 1; j >= 1; j--)
{
if (a[i][j])
{
f[i][j].right = f[i][l].left;
l = j;
}
}
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
if (a[i][j])
{
if (f[i][j].up >= v[i - 1][j - 1] && f[i][j].left >= v[i - 1][j - 1])
{
v[i][j] = v[i - 1][j - 1] + 1;
}
else
{
v[i][j] = min(f[i][j].up, f[i][j].left) + 1;
}
}
k = m - j + 1;
if (a[i][k])
{
if (f[i][k].up >= u[i - 1][k + 1] && f[i][k].right >= u[i - 1][k + 1])
{
u[i][k] = u[i - 1][k + 1] + 1;
}
else
{
u[i][k] = min(f[i][k].up, f[i][k].right) + 1;
}
}
maxx = max(maxx, max(v[i][j], u[i][k]));
}
cout << maxx;
//cout << u[3][4] << " " << u[4][3] << " " << u[5][2] << " - " << f[4][3].up << " - " << f[4][3].right;
}
by りゅうこせい @ 2018-09-18 19:22:02
一样一样。。我也是不知道怎么优化了
by 薄荷凉了夏 @ 2018-09-19 14:49:11
其实如果你的``` up!=0
就可以说明你这个位置上原来不是0
所以最开始的矩阵是没必要新开一个存下来的
SO 5个就OK了
by maruize @ 2019-11-30 22:26:32
把