HDU 4101 Ali and Baba

　　原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=4101

　　一看之下以为是博弈，后来分析才知道只是搜索题。

　　首先，我们需要从值为-1的位置由内向外搜索一次，标记出包围-1并且值不为0的最近一圈区域（这个临界区域记为A，那么A区域一旦在某个缺口打破，那么就可以定胜负了），如果发现此次搜索出了边界，那么肯定是Ali赢，否则进行以下步骤：从外围开始由外向内搜索，如果遇到非A区域的石头，总计和ans加上当前位置的HP，如果遇到的是A区域的石头，总计和ans加上当前位置HP-1（必须要留下一个HP，否则对方就赢了），最后求得的ans也就是Ali能够实施的合法步骤数，根据ans的奇偶性便能得出答案。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <string>
  4 #include <iostream>
  5 #include <math.h>
  6 #include <stdlib.h>
  7 #include <algorithm>
  8 #include <map>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 using namespace std;
 13 const int maxn = 300 + 5;
 14 typedef pair<int,int> pii;
 15 int g[maxn][maxn];
 16 bool h[maxn][maxn];  
 17 int dr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 18 bool vis[maxn][maxn];
 19 
 20 int N, M;
 21 int dx, dy; 
 22 
 23 struct node
 24 {
 25     int x, y;
 26 };
 27 
 28 bool bfs1()
 29 {
 30     memset(h, false, sizeof h);
 31     queue<node> que;
 32     node t;
 33     t.x = dx, t.y = dy;
 34     h[dy][dx] = true;
 35     que.push(t);
 36     while(!que.empty())
 37     {
 38         node cur = que.front();
 39         que.pop();
 40         int cx = cur.x;
 41         int cy = cur.y;
 42         for(int i = 0; i < 4; i++)
 43         {
 44             int nx = cx + dr[i][0];
 45             int ny = cy + dr[i][1];
 46             if(nx > 0 && nx <= M && ny > 0 && ny <= N)
 47             {
 48                 if(!h[ny][nx])
 49                 {
 50                     h[ny][nx] = true;
 51                     if(g[ny][nx] == 0)
 52                     {
 53                         t.x = nx, t.y = ny;
 54                         que.push(t);
 55                     }
 56                 }
 57             }
 58             else
 59                 return true;
 60         }
 61     }
 62     return false;
 63 }
 64 
 65 int bfs2()
 66 {
 67     memset(vis, false, sizeof vis);
 68     int ans = 0;
 69     queue<node> que;
 70     node s, t;
 71     s.x = 0, s.y = 0;
 72     vis[0][0] = true;
 73     que.push(s);
 74     while(!que.empty())
 75     {
 76         node cur = que.front();
 77         que.pop();
 78         int cx = cur.x;
 79         int cy = cur.y;
 80         for(int i = 0; i < 4; i++)
 81         {
 82             int nx = cx + dr[i][0];
 83             int ny = cy + dr[i][1];
 84             if(nx >= 0 && nx <= M + 1 && ny >= 0 && ny <= N + 1)
 85             {
 86                 if(!vis[ny][nx])
 87                 {
 88                     vis[ny][nx] = true;
 89                     if(!h[ny][nx])
 90                     {
 91                         ans += g[ny][nx];
 92                         t.x = nx, t.y = ny;
 93                         que.push(t);
 94                     }
 95                     else if(h[ny][nx] && g[ny][nx] > 0)
 96                     {
 97                         ans += g[ny][nx] - 1;
 98                     }
 99                 }
100             }
101         }
102     }
103     return ans;
104 }
105 
106 int main()
107 {
108     while(scanf("%d %d", &N, &M) != EOF)
109     {
110         memset(g, 0, sizeof g);
111         for(int i = 1; i <= N; i++)
112         {
113             for(int j = 1; j <= M; j++)
114             {
115                 scanf("%d", &g[i][j]);
116                 if(g[i][j] == -1)
117                     dx = j, dy = i;
118             }
119         }
120         if(bfs1())
121         {
122             puts("Ali Win");
123             continue;
124         }
125         int ans = bfs2();
126         if(ans & 1)
127             puts("Ali Win");
128         else
129             puts("Baba Win");
130     }
131     return 0;
132 }

View Code