求找错……

P1736 创意吃鱼法

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;
}

|