学步园

题目：题目链接

题意：题目意思就是两人玩扫雷，按照变换的规则。如果点着空地那么周围不包含数字的空地都会被触发。这样：把点

开空地时会打开的一大片区域看成一块，题目中说到，在一盘游戏中，一个格子不可能被翻开两次，说明任意两块空地

不会包含相同的格子。那么就可以看成一个组合游戏。当空地旁边没连任何数字的时候，sg = 1(直接转移到0)。如果

有一个数字，点空地可以转移到0，点数字可以转移到1，所以sg = 2。有2 个数字点空地转移到0，点数字转移到2，所

以sg = 1。以此类推，空地旁边有奇数个数字的时候，sg = 2，否则sg = 1。剩下的没与空地相连的数字，每个的sg

都是1。那么将所有空地的sg 异或起来，再异或(不与空地相连的数字个数对2取模)，等于零输出后手赢，大于0 输出

先手赢即可。

我们根据题目的数据，初始化0，有雷的标记，比如3，那么雷周围就标记为数字1.这样，我们找到一个空地0，如果这

个空地未被访问，那么就DFS一次，查找它所连接的数字的个数，并把记录过的数字标记。这样避免重复。最后，我们

在统计剩余的没有和空地相连的数字的个数，按照SG值取，最后看ans的情况就可以了：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
#pragma comment(linker,"/STACk:1024000000,1024000000")
using namespace std;

int map[1100][1100];
int f[8][2]= {{0,1},{0,-1},{-1,1},{-1,0},{-1,-1},{1,-1},{1,0},{1,1}};
int n,m;
int tmp;
int dfs(int i,int j)
{
    map[i][j] = 3;
    for(int k=0; k<8; k++)
    {
        int x = i + f[k][0];
        int y = j + f[k][1];
        if(x>=0&&y>=0&&x<m&&y<n)
        {
            if(map[x][y]==1)//数数字的个数
            {
                map[x][y] = 2;//标记已被取过
                tmp++;
            }
            else if(!map[x][y])
                dfs(x,y);
        }
    }
    return 0;
}

int main()
{
    int T, index;
    int ki;
    int i, j;
    int xi, yi;
    scanf("%d", &T);
    for(index = 1; index <= T; index++)
    {
        memset(map, 0, sizeof(map));
        int ans = 0;
        scanf("%d%d%d", &m, &n, &ki);
        for(i = 0; i < ki; i++)
        {
            scanf("%d%d", &xi, &yi);
            map[xi][yi] = 3;//有雷布置
            for(int k = 0; k < 8; k++)
            {
                int x=xi+f[k][0];
                int y=yi+f[k][1];
                if(x>=0&&y>=0&&x<m&&y<n)
                {
                    if(!map[x][y])
                        map[x][y]=1;//和雷相连置数字
                }
            }
        }
        for(i=0; i<m; i++)
        {
            for(j=0; j<n; j++)
                if(!map[i][j])//空地
                {
                    tmp=0;
                    dfs(i,j);
                    if(tmp&1)
                        ans^=2;
                    else
                        ans^=1;
                }
        }
        int ans1=0;

        for(i=0; i<m; i++)
        {
            for(j=0; j<n; j++)
            {
                if(map[i][j]==1)//求不与空地相连的数字
                    ans1++;
            }
        }
        ans1 %= 2;
        ans ^= ans1;
        printf("Case #%d: ",index);
        if(ans)
            printf("Xiemao\n");
        else
            printf("Fanglaoshi\n");
    }
    return 0;
}