HDU4678_Mine

很有意思，很好的題目。

這樣的，一個n*m的掃雷地圖，告訴你哪些地方是有雷的。一個人如果點在了空白處，那么與其相鄰的（八個方向）的數字以及空白都會遞歸地顯示出來，如果點在數字上面，那么就只會顯示這一個數字。

游戲過程中，誰第一個無法點開一個非雷的格子算輸。

這、、、、其實可以看成是nim博弈問題，但是有一點點點點的不同。

我們由于題目說明了數字的部分不會有重復的，所以我們把一個由空白部分連成的區域看成是一堆石子，那么有的單獨的數字就是一堆石子且只有一顆。

同時我們把所有的空白區域看成是一個石子，這樣問題就轉化為了給你N堆石子，以及每一堆的石子的數量，現在要你求出博弈的結果是先手勝還是后手勝？

由于每次可選擇的可以使一堆中的某一顆石子，也可以是一整堆的石子，所以這與單純的nim博弈是有所區別的。

其實可以這樣來考慮這個問題。

我們分別統計出石子數量為奇數的堆有多少個（x）、石子數為偶數的堆有多少個（y）。

那么其實，除非x和y均為偶數，否則先手必勝。

這樣來理解，其實博弈過程中，必勝者只要一直維護所有的石子數之和為偶數即可。

但是如果是一開始就為偶數偶數的話，那么就是必輸了。

不知道這么理解對不對呢？

?

?

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1010
using namespace std;int a[maxn][maxn],t,n,m,k,xi,yi,ans,cas=0,tot,flag;
bool b[maxn][maxn],vis[maxn][maxn];int dfs(int x,int y)
{if (a[x][y]==-1 || x<1 || x>n || y<1 || y>m) return 0;if (b[x][y]) return 0;b[x][y]=true;if (a[x][y]!=0) return 1;return dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1)+dfs(x-1,y-1)+dfs(x-1,y+1)+dfs(x+1,y-1)+dfs(x+1,y+1);
}int main()
{scanf("%d",&t);while (t--){memset(a,0,sizeof a);memset(b,false,sizeof b);memset(vis,false,sizeof vis);scanf("%d%d%d",&n,&m,&k);tot=0;while (k--){scanf("%d%d",&xi,&yi);xi+=1,yi+=1;vis[xi][yi]=true;}for (int i=1; i<=n; i++)for (int j=1; j<=m; j++){if (vis[i][j]){a[i][j]=-1;continue;}a[i][j]=0;for (int ii=-1; ii<=1; ii++)for (int jj=-1; jj<=1; jj++)if (vis[i+ii][j+jj]) a[i][j]++;}ans=0;for (int i=1; i<=n; i++)for (int j=1; j<=m; j++){if (b[i][j]) continue;if (a[i][j]==0){int tep=dfs(i,j)+1;if (tep&1) ans^=1;else ans^=2;tot++;}
            }for (int i=1; i<=n; i++)for (int j=1; j<=m; j++){if (b[i][j]) continue;if (a[i][j]==-1) continue;b[i][j]=true;ans^=1;tot++;
            }if (ans) printf("Case #%d: Xiemao\n",++cas);else printf("Case #%d: Fanglaoshi\n",++cas);}return 0;
}

?