hdu 4101（bfs+博弈）

题意：题目的意思就是说两个人轮流玩游戏，给你一张地图，这个地图中间有一点-1代表宝藏，Ali and Baba轮流走

路，如果某一个人能够直接走到宝藏的话，那么他就赢了。地图上其它的点0代表空地，数字代表当前地点的石子当

某一人拿石子的时候，他只能拿走一颗。问你谁最后能拿到宝藏；

解题思路：宝藏位于-1位置，如果能够直接找一条通路的话，那么肯定是Ali赢，这一步显然可以用bfs，只要出了边界的就有同路。如果没有的话，那么肯定这一条路径A被石头给围住了。那么我们首先把从宝藏位置引伸出来的路周围的所有石头标记了（这一步可以在第一次找通路的时候完成），接下来，如果这条路被包围的石头数都为1了，那么接下来取石头的人就会输，因为被包围的石头打通了。。所以直接计算出两人总共取石头的数量（不是全部取完，而是留下路径周围被1一个石头所包围），剩下的就是判断奇偶性就可以知道谁赢谁输了。。这道题确实转化得非常巧妙

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 310;
struct node
{
	int x,y;
};
int n,m,map[maxn][maxn],ans;
int dx,dy,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool has[maxn][maxn],vis[maxn][maxn];

bool bfs1()
{
	queue<node> q;
	node cur,nxt;
	cur.x = dx, cur.y = dy;
	q.push(cur);
	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		if(cur.x < 1 || cur.x > n || cur.y < 1 || cur.y > m) return true;
		for(int k = 0; k < 4; k++)
		{
			int i = cur.x + dir[k][0];
			int j = cur.y + dir[k][1];
			if(map[i][j] == 0)
			{
				map[i][j] = -1;
				nxt.x = i, nxt.y = j;
				q.push(nxt);
			}
			else if(map[i][j] > 0) has[i][j] = true;
		}
	}
	return false;
}

void bfs2()
{
	queue<node> q;
	node cur,nxt;
	cur.x = 0, cur.y = 0;
	vis[0][0] = true;
	q.push(cur);
	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		for(int k = 0; k < 4; k++)
		{
			int i = cur.x + dir[k][0];
			int j = cur.y + dir[k][1];
			if(i < 0 || i > n + 1 || j < 0 || j > m + 1 || vis[i][j]) continue;
			vis[i][j] = true;
			if(has[i][j] == false)
			{
				ans += map[i][j];
				nxt.x = i, nxt.y = j;
				q.push(nxt);
			}
			else ans += map[i][j] - 1;
		}
	}
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		memset(has,false,sizeof(has));
		memset(vis,false,sizeof(vis));
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j] == -1)
					dx = i, dy = j;
			}
		if(bfs1())
		{
			printf("Ali Win\n");
			continue;
		}
		ans = 0;
		bfs2();
		if(ans & 1)
			printf("Ali Win\n");
		else printf("Baba Win\n");
	}
	return 0;
}