hdu2873 Bomb Game

2024-05-14 12:18
文章标签 game bomb hdu2873

本文主要是介绍hdu2873 Bomb Game,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Bomb Game

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 440 Accepted Submission(s): 206


Problem Description
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
可以直接根据sg 函数,直接打表求出sg的值 ,这样就可以转化成一般的nim游戏了!

sg函数的定义:

首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图,定义关于图的每个顶点的SG函数如下:sg(x)=mex{ sg(y) | y是x的后继 },即一个节点的sg函数值等于其所有后继结点的sg函数值集合的mex

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define M 55
int pri[M][M],map[10000];
int getsg(int a,int b){int i,j;mem(map,0);for(i=0;i<a;i++)for(j=0;j<b;j++){map[pri[a][j]^pri[i][b]]=1;}for(i=0;;i++){if(!map[i])return i;}
}
int main()
{int n,m,ans,i,j;char c;mem(pri,-1);for(i=0;i<M;i++)pri[0][i]=pri[i][0]=i;for(i=1;i<M;i++)for(j=1;j<M;j++){pri[i][j]=getsg(i,j);}while(scanf("%d%d",&n,&m)!=EOF&&n+m){getchar();for(ans=0,i=0;i<n;i++){for(j=0;j<m;j++){c=getchar();if(c=='#'){ans^=pri[i][j];}}getchar();}if(ans)printf("John\n");else printf("Jack\n");}return 0;
}


这篇关于hdu2873 Bomb Game的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988728

相关文章

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

10400 -Game Show Math

这道题的话利用了暴力深搜,尽管给了20S,但是这样还会超时,所以就需要利用回溯进行减枝,因为是DFS,所以用一个数组vis[i][j]记录是否在状态i时候取到过j值,如果取到过的话,那么直接回溯(往后搜索已经没有意义了,之前到达这个状态的时候是无法得到结果的) 还有需要注意的地方就是题目的要求,每一步的结构都在(-32000,32000)之间,所以需要一步判断,如果在这个范围外直接回溯 最后一

【POJ】1733 Parity game 并查集

传送门:【POJ】1733 Parity game 题目大意:给你一个长度为n的01序列,再给你m句话,每句话是一个区间【L,R】,告诉你区间【L,R】中1的个数,现在你的任务是找到从第几句话开始说的和前面矛盾,出现第一次假话的时候前面有多少是真话。 题目分析:一开始看几乎没思路啊。后来没办法了,只能跑别人的博客去看看了。。。一看到说把一个区间【L,R】拆成两个区间【0,L-1】,

【HDU】5426 Rikka with Game【DP】

题目链接:【HDU】5426 Rikka with Game #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;const int MAXE = 200005 ;

LeetCode 45 Jump Game II

题意: 给出一个步长数组nums,如果一个人站在i这个点上那么他可以向右最多走nums[i]步,求从左端点走到右端点的最少步数。 思路: 如果点x可以用dp[x]步到达,那么[ x + 1, x + nums[x] ]区间内的点都可以用dp[x] + 1步到达。 利用这个想法,可以O(n)的求出走一步可以到达哪些位置,走两步可以到达哪些位置,以此类推。 代码: clas

【论文笔记】Multi-Task Learning as a Bargaining Game

Abstract 本文将多任务学习中的梯度组合步骤视为一种讨价还价式博弈(bargaining game),通过游戏,各个任务协商出共识梯度更新方向。 在一定条件下,这种问题具有唯一解(Nash Bargaining Solution),可以作为多任务学习中的一种原则方法。 本文提出Nash-MTL,推导了其收敛性的理论保证。 1 Introduction 大部分MTL优化算法遵循一个通用方

android-Intent,Injector,Template,Adapter,Validation,Gesture,Game,Game Engine,Bluetooth...

Intent Intent PhotoPicker 图片选择 & 图片预览https://github.com/donglua/PhotoPicker Injector AndroidAnnotations Fast Android Development. Easy maintainance. https://github.com/excilys/androidannotations

HDU5515 Game of Flying Circus(二分)

题意:题解有翻译,然后自己拦截对手时候可以任意走,当然是直线最快啦 题解:http://www.cnblogs.com/qscqesze/p/4931912.html #include<bits/stdc++.h>using namespace std;#define LL long long#define pb push_back#define X first#define Y

bomb 实验

GDB常用命令: GDB调试常用命令-CSDN博客 原理: 编译与反汇编过程-CSDN博客 Bomb实验实现 阶段一:  分析 分配空间:sub $0x8,%rsp 为局部变量分配栈空间。设置参数:mov $0x402400,%esi 将字符串地址加载到 %esi。比较字符串:call 401338 <strings_not_equal> 调用函数比较字符串。判断结果:test %e

hdu 1846 Brave Game 巴什博奕

Description 十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:Zathura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。  今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”,这也是我命名这个题目的原因。  当然,除了