HDU4101 Ali and Baba （bfs+dfs+博弈）

本文主要是介绍HDU4101 Ali and Baba （bfs+dfs+博弈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： Ali 和Baba玩游戏，游戏是在给出的一个n*m的图中，有且仅有一个宝藏（-1）表示，图中其他位置可能是空地（0表示），也可能是石头（石头的HP用一个正数表示）。二人轮流，每次游戏开始都是Ali先手，选手可以攻击石头，每次可以让石头HP减少一。问Ali是否可以胜利。
开始时，直接BFS 宝藏能扩展的最大的面积，因为面对都是1包围的-1 ，这个是必败态。但是WA了；然后想了很久，想到，可能存在宝藏所形成的连通的块是个环形，把其他的石头包围在里面，这样，这些石头就等于是没用的了。所以不得不多写了一个BFS_ans()

#include<bits/stdc++.h>
#define cl(a,b) memset(a,b,sizeof(a));
#define LL long long
#define P pair<int,int>
#define X first
#define Y second
#define out(x) cout<<x<<endl;
using namespace std;
const int maxn=305;
const int inf=9999999;int n,m;
int a[maxn][maxn];
bool vis[maxn][maxn];int dir[][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool pan(P s){if(s.X>=0&&s.X<=n+1&&s.Y>=0&&s.Y<=m+1)return true;return false;
}
void bfs(int x,int y){//标记宝藏形成的连通的块cl(vis,false);queue<P> q;q.push(P(x,y));vis[x][y]=true;while(!q.empty()){P s=q.front();q.pop();for(int i=0;i<4;i++){P tmp=s;tmp.X+=dir[i][0];tmp.Y+=dir[i][1];if(pan(tmp)&&!vis[tmp.X][tmp.Y]){vis[tmp.X][tmp.Y]=true;if(a[tmp.X][tmp.Y]==0)q.push(tmp);}}}
}
bool vis1[maxn][maxn];int bfs_ans(){cl(vis1,false);queue<P> q;q.push(P(0,0));vis1[0][0]=true;int ans=0;while(!q.empty()){P s=q.front();q.pop();for(int i=0;i<4;i++){P tmp=s;tmp.X+=dir[i][0];tmp.Y+=dir[i][1];if(pan(tmp)&&!vis1[tmp.X][tmp.Y]){if(vis[tmp.X][tmp.Y]){if(a[tmp.X][tmp.Y]>1)ans+=a[tmp.X][tmp.Y]-1;}else {ans+=a[tmp.X][tmp.Y];q.push(tmp);}vis1[tmp.X][tmp.Y]=true;}}}return ans;
}bool used[maxn][maxn];
bool dfs(int x,int y){//查找是否存在一个直达的路径if(x==1||x==n||y==1||y==m){return true;}for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(pan(P(xx,yy))&&!used[xx][yy]&&a[xx][yy]==0){used[xx][yy]=true;if(dfs(xx,yy))return true;//used[xx][yy]=false;}}return false;
}int main(){while(~scanf("%d%d",&n,&m)){int si,sj;cl(a,0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);if(a[i][j]==-1){si=i;sj=j;}}}if(si==1||si==n||sj==1||sj==m){puts("Ali Win");continue;}cl(used,0);if(dfs(si,sj)){puts("Ali Win");continue;}bfs(si,sj);//printf("===%d\n",bfs_ans());if(bfs_ans()&1){puts("Ali Win");}else {puts("Baba Win");}}return 0;
}
/*
4 4
1 1 1 1
1 1 0 1
1 1 -1 1
1 1 1 1
3 3
1 1 1
1 -1 1
1 1 1
4 4
1 1 0 1
1 1 0 1
1 1 -1 1
1 1 1  1
*/