开闸放水 @ 2017-06-16 21:12:55
错一个点……求高人指教……
思路就是对每个格子每次检查一下那一行那一列的正方形是不是都是空的,是的话那个点的对角线最大值就加上上一行的点的值
f[0][i][j]是左上右下对角线的最大值……f[1][i][j]就是右上左下了
#include <iostream>
#include <string.h>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int min(int a,int b,int c,int d)
{
return min(min(a,b),min(c,d));
}
int max(int a,int b,int c)
{
return max(max(a,b),c);
}
int n,m,a[2501][2501],f[2][2502][2502],ans=0;//f[0][i][j] is the top-left diagonal
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j])
{
f[0][i][j]=f[1][i][j]=1;
int flag0=1,flag1=1;
for(int k=1;k<=f[0][i-1][j-1];k++)
if(a[i][j-k]||a[i-k][j])
flag0=0;
for(int k=1;k<=f[1][i-1][j+1];k++)
if(a[i][j+k]||a[i-k][j])
flag1=0;
if(flag0>0)
f[0][i][j]+=f[0][i-1][j-1];
if(flag1>0)
f[1][i][j]+=f[1][i-1][j+1];
ans=max(ans,f[0][i][j],f[1][i][j]);
}
printf("%d\n",ans);
}
by matsuk @ 2018-08-19 20:00:01
然而我的80分是没有通过不把0的个数+1得到的