两次广搜

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=305;int N,M,Sx,Sy;int Map[maxn][maxn];int Y[maxn][maxn];int e[maxn][maxn];int flag[maxn][maxn];int Flag[maxn][maxn];int F[maxn][maxn];int dir[4][2]={
   {-1,0},{
   1,0},{
   0,-1},{
   0,1}};int ans,sum;struct Point{    int x,y;    Point(int a,int b){x=a;y=b;}};void init(){    memset(flag,0,sizeof flag);//标记有没有走过    memset(F,0,sizeof F);//标记是否是边界    memset(Map,0,sizeof Map);    memset(Flag,0,sizeof Flag);    memset(e,0,sizeof e);    memset(Y,0,sizeof Y);    ans=-1,sum=0;}void read(){    for(int i=1;i<=N;i++)        for(int j=1;j<=M;j++)        {            scanf("%d",&Map[i][j]);            Y[i][j]=Map[i][j];        }}void bfs1(){    queue
          
           Q; Point p(Sx,Sy); flag[Sx][Sy]=1; Q.push(p); while(!Q.empty()) { Point p=Q.front(); Q.pop(); if(Map[p.x][p.y]!=0&&Map[p.x][p.y]!=-1) { F[p.x][p.y]=1;//边界标1 continue; } for(int i=0;i<4;i++) { int NewX=p.x+dir[i][0]; int NewY=p.y+dir[i][1]; if(!flag[NewX][NewY]) if(NewX>=1&&NewX<=N) if(NewY>=1&&NewY<=M) { flag[p.x][p.y]=1; Point p(NewX,NewY); Q.push(p); } } } /* for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) printf("%d",F[i][j]); printf("\n"); } */}void bfs2(){ queue
           
            Q; Point p(0,0); Flag[0][0]=1; Q.push(p); while(!Q.empty()) { Point p=Q.front(); Q.pop(); //printf("%d %d %d\n",p.x,p.y,Map[p.x][p.y]); if(Map[p.x][p.y]) { if(F[p.x][p.y]) { sum=sum+Map[p.x][p.y]-1; continue; } else sum=sum+Map[p.x][p.y]; } for(int i=0;i<4;i++) { int NewX=p.x+dir[i][0]; int NewY=p.y+dir[i][1]; if(Flag[NewX][NewY]==0) if(NewX>=0&&NewX<=N+1) if(NewY>=0&&NewY<=M+1) { Flag[NewX][NewY]=1; Point p(NewX,NewY); Q.push(p); } } }}void dfs(int x,int y){ if(x==0||x==N+1||y==0||y==M+1) {ans=1;return;} e[x][y]=1; for(int i=0;i<4;i++) { int NewX=x+dir[i][0]; int NewY=y+dir[i][1]; if(Y[NewX][NewY]==0) if(e[NewX][NewY]==0) dfs(NewX,NewY); }}void solve(){ for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(Map[i][j]==-1) Sx=i,Sy=j; e[Sx][Sy]=1;dfs(Sx,Sy); if(ans==1){printf("Ali Win\n");return;} bfs1(); bfs2(); // printf("%d\n",sum); if(sum%2==1) printf("Ali Win\n"); else printf("Baba Win\n");}int main(){ while(~scanf("%d%d",&N,&M)) { init(); read(); solve(); } return 0;}