程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2873 Bomb Game-----sg

hdu2873 Bomb Game-----sg

編輯:C++入門知識

Bomb Game
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 353    Accepted Submission(s): 165


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

Source
2009 Multi-University Training Contest 8 - Host by BJNU

Recommend
gaojie
 
這題A的我好辛苦,題目所說的1是我們輸入的矩陣的0,即(1,1)這個位置是我們輸入的矩陣的(0,0)位置,暈死,我直接想死了。
[cpp]
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
#include<memory.h> 
using namespace std; 
int sg[60][60]; 
char str[60][60]; 
int num[600]; 
int dfs(int x,int y) 

    memset(num,-1,sizeof(num)); 
    for(int i=0;i<x;i++) 
    for(int j=0;j<y;j++) 
    { 
        num[sg[i][y]^sg[x][j]]=1; 
    } 
    for(int i=0;;i++) 
    if(num[i]==-1) return i; 

int main() 

    for(int i=0;i<=50;i++) 
    sg[0][i]=sg[i][0]=i; 
    for(int i=1;i<=50;i++) 
    for(int j=1;j<=50;j++) 
    sg[i][j]=dfs(i,j); 
    int n,m; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        if(n==0&&m==0) break; 
        int ans=0; 
        for(int i=0;i<n;i++) 
        { 
            scanf("%s",str[i]); 
            for(int j=0;j<m;j++) 
            { 
                if(str[i][j]=='#') 
                { 
                    ans^=sg[i][j]; 
                } 
            } 
        } 
        if(ans) puts("John"); 
        else puts("Jack"); 
    } 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved