学步园

题意： 两个人一起玩扫雷，都不点炸弹，谁先不能点谁就输。问谁赢。

解法： 在题目保证不出现重叠的情况下，就可以转化为类似取石子的Nim游戏（取1个或者取整堆）。其他部分看题解的，这里略过。

第一次做博弈题，大概了解了一下这类题的思路。下面描述一下简单Nim博弈的解法。

对于n堆石子，它的子游戏是一堆石子，通过分析一堆石子的SG值，将所有堆对应的SG值异或，得到的结果非0为先手赢，0为后手赢。

这类题如果纯推演的话，是很复杂的，所以要借助SG定理。（SG定理的证明这里略过，实在是被博弈惨虐，不求甚解，知道怎么用就可以了ORZ）。

SG值的定义：SG值是对于一个状态，他的所有后继状态的SG值之外的最小非负整数。

对于必败状态，它的SG值为0。必胜状态的SG值为非0。

Nim游戏的每一个状态的值，都是确定的，不是必胜就是必败。

必胜状态：存在至少一个后继为必败状态。

必败状态：所有的后继状态均为必胜状态或者没有后继状态。

所以每一个非末状态的SG值都是可以通过后继状态推知，末状态的SG值通常为0。

然后就是寻找SG值的规律，推出结论，秒题。

注意在抽象出取石子模型之后的一些特殊细节。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))

int dir[8][2] = {1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
int g[1100][1100];
int n,m,k;
struct Q {
    int x, y;
}q[1001000],f,e;

int bfs(int x, int y) {
    int qf,qe;
    int ret = 0;
    qf = qe = 0;
    q[0].x = x;
    q[0].y = y;
    g[x][y] = -2;
    while(qf <= qe) {
        f = q[qf++];
        for(int i=0; i<8; i++) {
            int dx = f.x + dir[i][0];
            int dy = f.y + dir[i][1];
            if(dx<0 || dx>=n || dy<0 || dy>=m || g[dx][dy] < 0) continue;
            if(g[dx][dy] > 0) {
                ret ++;
            }
            else {
                q[++qe].x = dx;
                q[qe].y = dy;
            }
            g[dx][dy] = -2;
        }
    }
    return ret;
}

int main() {
    int cas, ca = 0;
    scanf("%d", &cas);
    int x,y;
    while(cas--) {
        scanf("%d%d%d", &n, &m, &k);
        clr(g,0);
        while(k--) {
            scanf("%d%d", &x, &y);
            g[x][y] = -1;
            for(int i=0; i<8; i++) {
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                if(dx<0 || dx>=n || dy<0 ||dy>=m || g[dx][dy] < 0) continue;
                g[dx][dy] = 1;
            }
        }

        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(g[i][j] == 0) ans ^= bfs(i,j)%2+1;
            }
        }
        int tot = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(g[i][j] > 0) tot++;
            }
        }
        ans ^= tot&1;

        if(ans) printf("Case #%d: Xiemao\n",++ca);
        else printf("Case #%d: Fanglaoshi\n",++ca);
    }
    return 0;
}