wjzcom @ 2016-11-16 15:17:47
//luogu 1736 wjz3 dp 1611161450
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2500 + 10;
int n, m;
int map[MAXN][MAXN], dd[MAXN][MAXN], f[MAXN][MAXN]; //dd:计算0时需要用到
struct dis
{
int x, y;
} d[MAXN][MAXN]; //用于计算所有的0横轴和纵轴的最大连续距离
int main()
{
cin >> n >> m;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
dd[i][j] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin >> map[i][j];
dd[i][j] = map[i][j];
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(map[i][j]) f[i][j] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
d[i][j].x = d[i][j].y = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) if(dd[i][j] == 0)
{
if(dd[i][j-1] == 0) d[i][j].x = d[i][j-1].x + 1;
if(dd[i-1][j] == 0) d[i][j].y = d[i-1][j].y + 1;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(map[i][j])
if(!map[i][j-1] && !map[i-1][j] && map[i-1][j-1])
{
int u = f[i-1][j-1];
int v = min(f[i-1][j-1], min(d[i-1][j].y, d[i][j-1].x));
f[i][j] = v + 1;
}
int maxx = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
maxx = max(maxx, f[i][j]);
if(map[i][j]) f[i][j] = 1;
else f[i][j] = 0;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
d[i][j].x = d[i][j].y = 1;
for(int i = 1; i <= n; i++)
for(int j = m; j >= 1; j--) if(dd[i][j] == 0)
{
if(dd[i][j+1] == 0) d[i][j].x = d[i][j+1].x + 1;
if(dd[i-1][j] == 0) d[i][j].y = d[i-1][j].y + 1;
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= 1; j--)
if(map[i][j])
if(!map[i][j+1] && !map[i-1][j] && map[i-1][j+1])
{
int u = f[i-1][j+1];
int v = min(f[i-1][j+1], min(d[i-1][j].y, d[i][j+1].x));
f[i][j] = v + 1;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
maxx = max(f[i][j], maxx);
cout << maxx;
system("pause");
return 0;
}
by psk2016 @ 2017-07-13 16:02:11
@wjzcom 你开的数组太大了(最大128.9MB)!建议调小一点MAXN,或者换一个更优的算法。
by c201904 @ 2017-07-30 10:56:30
把maxn调为2501