首页 > ACM题库 > HDU-杭电 > HDU 2873-Bomb Game[解题报告]HOJ
2014
02-17

HDU 2873-Bomb Game[解题报告]HOJ

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.

输入:

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.

输出:

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.

样例输入:

2 2
.#
..
2 2
.#
.#
0 0

样例输出:

John
Jack

#include<cstdio>
#include<cstring>

int sg[55][55];
char s[55][55];

int dfs(int p,int q)
{
 if(~sg[p][q]) return sg[p][q];
 bool vis[3333];memset(vis,0,sizeof(vis));
 if(!p) for(int v=0;v<q;v++) vis[dfs(p,v)]=1;
 if(!q) for(int u=0;u<p;u++) vis[dfs(u,q)]=1;
 for(int u=0;u<p;u++) for(int v=0;v<q;v++) vis[dfs(u,q)^dfs(p,v)]=1;
 int i=0;while(vis[i]) i++;
 return sg[p][q]=i;
}
int main()
{
 memset(sg,-1,sizeof(sg));
 int n,m;
 while(scanf("%d%d",&n,&m),n||m)
 {
 int g=0;
 for(int i=0;i<n;i++) scanf("%s",s[i]);
 for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(s[i][j]=='#') g^=dfs(i,j);
 puts(g?"John":"Jack");
 }
 return 0;
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。