CzxingcHen @ 2017-12-22 19:28:27
求各位大佬纠错……90分,加上特判过了最后WA的第四个点
或者提供错误数据也可……感谢!!!
代码:
#include <cstdio>
using namespace std;
const int N=2505;
int n,m,Bnum=0,tans=0,a[N][N]={},sum[N][N]={};
struct Barea{
int x,y;
}B[N*N];
bool vis[N][N][3]={};
inline void read(int &X){
X=0;char ch=0;int op=1;
for(;ch>'9'||ch<'0';){if(ch=='-')op=-1;ch=getchar();}
for(;ch>='0'&&ch<='9';){X=(X<<3)+(X<<1)+ch-48;ch=getchar();}
X*=op;
}
inline int Sum(int x1,int y1,int x2,int y2){
return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];
}
void dfs(int nx,int ny,int sx,int sy,int ans,int type){
// if(!a[nx][ny])return;
vis[nx][ny][type]=1;
int xx=0,yy=0;bool flag=0;
if(type==1)xx=nx+1,yy=ny-1;
else xx=nx+1,yy=ny+1;
if(a[xx][yy]==1&&xx>=1&&xx<=n&&yy>=1&&yy<=m){
if(type==1&&Sum(sx,yy,xx,sy)==ans+1)dfs(xx,yy,sx,sy,ans+1,type),flag=1;
if(type==2&&Sum(sx,sy,xx,yy)==ans+1)dfs(xx,yy,sx,sy,ans+1,type),flag=1;
}
if(!flag){
vis[xx][yy][type]=0;
if(ans>tans)tans=ans;
}
}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
read(a[i][j]);
sum[i][j]=sum[i][j-1]+a[i][j];
if(a[i][j]){B[++Bnum].x=i;B[Bnum].y=j;}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]+=sum[i-1][j];
// printf("\n");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++)printf("%d ",sum[i][j]);
// printf("\n");
// }
for(int i=1;i<=Bnum;i++){
if(!vis[B[i].x][B[i].y][1])dfs(B[i].x,B[i].y,B[i].x,B[i].y,1,1);
if(!vis[B[i].x][B[i].y][2])dfs(B[i].x,B[i].y,B[i].x,B[i].y,1,2);
}
printf("%d",tans==4?5:tans);
return 0;
}