HDU-2873 Bomb Game

心已赠人 2022-06-10 10:25 149阅读 0赞

##                                     Bomb Game    ##

## John and Jack, two mathematicians, created a game called “Bomb Game” at spared time. This game is played on an n\*m chessboard. A pair of integers (p, q) represents the grid at row p, column q. Some bombs were placed on the chessboard at the beginning. Every round, a player can choose to explode a bomb located at (p, q), and the exploded bomb will disappear. Furthermore:       1.If p>1 and q>1, the bomb will split up into two bombs located at (u, q) and (p, v), u<p, v<q, u and v are chosen by the player.    2.If p=1 and q>1, one new bomb will be produced, located at (p, v), v<q, v can be chosen freely by the player.    3.If q=1 and p>1, one new bomb will be produced, located at (u, q), u<p, u can be chosen freely by the player.          If two bombs located at the same position or a bomb located at (1, 1), they will be exploded automatically without producing new bombs.    Two players play in turn, until one player cannot explode the bombs and loses the game.    John always plays first.    Now, we’ll give you an initial situation, and you should tell us who will win at last. Assume John and Jack are smart enough, and they always do the best choice.  Input  There are several test cases, each one begins with two integers n and m, 0<n, m<=50, represents the number of rows and columns. Following by an n\*m grid, describing the initial situation, ‘\#’ indicates bomb.    The input is terminated by n=m=0.  Output  For each test case, output one line, the name of the winner.  Sample Input  2 2 .\# .. 2 2 .\# .\# 0 0  Sample Output  John Jack      ##

题意：给你一个n∗m的棋盘，棋盘上会存在一些炸弹，每次可以选择引爆一颗炸弹，这个炸弹爆炸后会分成两个炸弹，分别到当前位置的上方和左方，如果处于边界则产生一个炸弹,且炸弹爆炸后会消失，谁不能引爆了谁输。

思路：因为每次引爆炸弹后，一个炸弹变成两个炸弹，所以这是一个游戏变成多个子游戏的题目，也就是multi-SG，每一个后继情况对应的SG值就是两个子游戏的SG值的异或，然后我们把所有可能的后继情况遍历一遍，就可以得到目前状况下的SG值。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 10005;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    char MAP;
    int SG[60][60];
    int vis[MAXN];
    
    int getSG(int a, int b)
    {
    	if (SG[a][b] != -1)
    		return SG[a][b];
    	memset(vis, 0, sizeof vis);
    	for (int i = 1; i < a; i++)
    	{
    		for (int j = 1; j < b; j++)
    		{
    			SG[a][b] = (getSG(i,b) ^ getSG(a,j));
    			vis[SG[a][b]] = 1;
    		}
    	}
    	for (int i = 0; ; i++)
    	{
    		if (!vis[i])
    			return SG[a][b] = i;
    	}
    }
    
    void init()
    {
    	memset(SG, -1, sizeof SG);
    	for (int i = 1; i <= 55; i++)
    	{
    		SG[1][i] = i - 1;
    		SG[i][1] = i - 1;
    	}
    	for (int i = 1; i <= 55; i++)
    	{
    		for (int j = 1; j <= 55; j++)
    		{
    			SG[i][j] = getSG(i,j);
    		}
    	}
    }
    
    int main()
    {
    	int n, m;
    	int ans;
    	init();
    	while (scanf("%d%d",&n,&m)!=EOF,n||m)
    	{
    		ans = 0;
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j <= m; j++)
    			{
    				scanf(" %c", &MAP);
    				if (MAP == '#')
    					ans ^= SG[i][j];
    			}
    		}
    		if (ans == 0)
    			printf("Jack\n");
    		else
    			printf("John\n");
    	}
    }