hdu 4101 Ali and Baba （bfs+严密思维）

Ali and BabaTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 971    Accepted Submission(s): 225

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>#define maxn 405using namespace std;int n,m,ans;int cnt1,cnt2;int sx,sy;int dx[]= {-1,1,0,0};int dy[]= {0,0,-1,1};int mp[maxn][maxn];int vis[maxn][maxn],vis1[maxn][maxn];struct Node{ int x,y;} cur,now,q[maxn*maxn];bool bfs1(){ int i,j,nx,ny,tx,ty; int head=0,tail=-1; memset(vis,0,sizeof(vis)); cur.x=sx; cur.y=sy; vis[sx][sy]=1; q[++tail]=cur; while(head<=tail) { now=q[head]; head++; nx=now.x; ny=now.y; for(i=0; i<4; i++) { tx=nx+dx[i]; ty=ny+dy[i]; if(tx<1||tx>n||ty<1||ty>m) return true ; if(vis[tx][ty]) continue ; if(mp[tx][ty]) { vis[tx][ty]=2; continue ; } cur.x=tx; cur.y=ty; vis[tx][ty]=1; q[++tail]=cur; } } return false ;}void bfs2(){ int i,j,nx,ny,tx,ty; int head=0,tail=-1; memset(vis1,0,sizeof(vis1)); for(i=0;i<=n+1;i++) { cur.x=i; cur.y=0; vis1[i][0]=1; q[++tail]=cur; cur.y=m+1; vis1[i][m+1]=1; q[++tail]=cur; } for(j=1;j<=m;j++) { cur.x=0; cur.y=j; vis1[0][j]=1; q[++tail]=cur; cur.x=n+1; vis1[n+1][j]=1; q[++tail]=cur; } while(head<=tail) { now=q[head]; head++; nx=now.x; ny=now.y; for(i=0; i<4; i++) { tx=nx+dx[i]; ty=ny+dy[i]; if(tx<0||tx>n+1||ty<0||ty>m+1||vis1[tx][ty]) continue ; if(vis[tx][ty]==2) { vis1[tx][ty]=2; continue ; } cur.x=tx; cur.y=ty; vis1[tx][ty]=1; q[++tail]=cur; } }}bool solve(){ int i,j; cnt1=cnt2=0; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { if(!vis[i][j]&&vis1[i][j]) cnt1+=mp[i][j];// 从里到外访问不到且从外到里能访问到 else if(vis[i][j]==2&&vis1[i][j]==2) cnt2=cnt2+mp[i][j]-1; // 环 } } printf("%d\n",cnt1+cnt2); if((cnt1+cnt2)&1) return true ; return false ;}int main(){ int i,j; while(~scanf("%d%d",&n,&m)) { for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%d",&mp[i][j]); if(mp[i][j]==-1) sx=i,sy=j; } } if(bfs1()) printf("Ali Win\n"); else { bfs2(); if(solve()) printf("Ali Win\n"); else printf("Baba Win\n"); } } return 0;}/*环中有数6 71 1 1 1 1 1 11 0 0 0 0 0 11 0 3 5 1 1 11 0 -1 4 0 1 11 0 1 0 0 1 11 1 1 1 1 1 1环中有环7 71 1 1 1 1 1 11 1 0 0 0 0 11 0 0 1 0 0 11 0 1 1 1 0 11 0 0 1 0 0 11 0 0 -1 0 0 11 1 1 1 1 1 1ans:166*/