本文主要是介绍hdu 2873 Bomb Game 【博弈-预处理表】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目传送！！！
题意：
n*m的格子内，有些格子里有炸弹，A和B轮流操作，不能操作的人输。操作如下：若位置（p,q）有炸弹
（1）p>1,q>1可以任选u<p,v<q，把炸弹分成两个分别位于(u,q),(p,v)。
（2）p==1,任选v<q,把炸弹移动到(p,v)
（3）q==1,任选u<p把炸弹移动到(u,q)
（4）另外，如果一个格子有两个炸弹，则两个炸弹抵消掉，或者某则炸弹被移到（1,1），该炸弹将直接消失。
给定一个图，求是否必胜？
解题思路：
这题其实我是猜的，先假设两个炸弹在一起不会消失，那么每个炸弹的操作是互不干涉的，可以看成多个游戏的组合，
剩下的就简单了，跟普通的NIM博弈一样，记忆化求NIM值就可以了。再来考虑，两个炸弹合并会消失与不消失的等价性，如果不消失的话，有两个一样位置的炸弹，他们的状态是一样的，针对这两两个炸弹，A或者B动其中一个都是没必要的，因为若其中一人动其中一个炸弹的话，另外一个人只需要对另外一个做同样操作就可以回到原来的状态，所两个位置相同的炸弹的存在是没有必要的，可以视为他们相互抵消了。
解题代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
#include<list>
#include<bitset>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef bitset<800> B;
#define INF 0x3f3f3f3f
int dp[55][55];
int dfs(int r,int c)
{B b;if(dp[r][c]!=-1) return dp[r][c];if(r==1&&c==1) return 0;for(int i=1;i<r;i++)for(int j=1;j<c;j++){int rr=dfs(i,c)^dfs(r,j);b.set(rr);}if(r==1){for(int j=1;j<c;j++) b.set(dfs(r,j));}if(c==1)for(int i=1;i<r;i++) b.set(dfs(i,c));int p=0;while(b[p]) p++;return dp[r][c]=p;
}
int n,m;
char mp[55][55];
int main()
{memset(dp,-1,sizeof dp);while(~scanf("%d%d",&n,&m)&&n+m){getchar();for(int i=0;i<n;i++)gets(mp[i]);int ans=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(mp[i][j]=='#') ans^=dfs(i+1,j+1);}if(ans) puts("John");else puts("Jack");}return 0;
}
这篇关于hdu 2873 Bomb Game 【博弈-预处理表】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
