HDU 2873 Bomb Game

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

题意：在一个二维的棋盘上有一些炸弹，每一步可以选择引爆一个炸弹，这些炸弹(x,y)分三种情况：

1、x,y>1 , 那么引爆后会在 (u, y) 和(x, v)位置产生两个新的炸弹， u<x, v<y，u，v自选。

2、x = 1 ， y > 1，引爆后仅在(1,v)位置产生一个新的炸弹，v<y，v自选。

3、x>1 , y = 1，和上一条同理。

如果两个炸弹在同一个位置或在(1,1)位置时，它们会自动爆炸。

其实在同一个位置这一条不用管的，想想我们组合游戏计算sg值就是把各个单一游戏的sg值异或起来，两个同位置的sg值一定是一样的，所以异或起来也是0，即不用管。

现在我们考虑把这个游戏拆成仅单点(x,y)有炸弹的单一游戏。

首先我们考虑特殊情况(1,1)处的sg值肯定为0，那么对于(1,i)和(i,1)的sg值就为i-1，因为可以转移到任意的(1,j)和(j,1)（j<i）。

那么就可以把剩下的情况sg值计算出来了。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <utility>
using namespace std;

#define rep(i,j,k) for (int i=j;i<=k;i++)
#define Rrep(i,j,k) for (int i=j;i>=k;i--)

#define Clean(x,y) memset(x,y,sizeof(x))
#define LL long long
#define ULL unsigned long long
#define inf 0x7fffffff
#define mod 100000007
const int maxn = 55;
int sg[maxn][maxn];

void init()
{
    bool f[maxn*maxn];
    rep(i,1,50) sg[i][1] = i-1;
    rep(i,1,50) sg[1][i] = i-1;
    rep(i,2,50)
        rep(j,2,50)
        {
            Clean(f,false);
            rep(x,1,i-1)//枚举所有可以转移的情况
                rep(y,1,j-1)
                f[ sg[x][j] ^ sg[i][y] ] = true;
            int k = 0;
            while( f[k] ) k++;
            sg[i][j] = k;
        }
}

int main()
{
    int n,m;
    char c;
    init();
    while( cin>>n>>m )
    {
        if ( n + m == 0 ) break;
        int ans = 0;
        rep(i,1,n)
        {
            getchar();
            rep(j,1,m)
            {
                c = getchar();
                if ( c == '#' )
                    ans ^= sg[i][j];
            }
        }
        puts( ans ? "John" : "Jack" );
    }
    return 0;
}