2016-07-18 108 views
-1

https://www.hackerrank.com/challenges/chessboard-game-again-1棋盘游戏...但不同的一个

我曾尝试通过以下方式对上述问题,但答案被评估为错误的。(我不是要求一个解决方案,但我问了方法中的缺陷);

我的代码(请忽略C99错误)

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 
int numofmov = 0; 
int issafe(int a,int b){ 
    if(a>=0 && a<15 && b>=0 && b<15) 
     return 1; 
    return 0; 
} 
void move(int board[][15]){ 
    for(int i=0;i<15;i++){ 
     for(int j=0;j<15;j++){ 
      if(board[i][j]>0){ 
       board[i][j]--; 
       if(issafe(board,i-2,j+1)==1) { 
        numofmov++; 
        board[i-2][j+1]++; 
       } 
       if(issafe(board,i-2,j-1)==1) { 
        numofmov++; 
        board[i-2][j-1]++; 
       }     
       if(issafe(board,i+1,j-2)==1) { 
        numofmov++; 
        board[i+1][j-2]++; 
       } 
       if(issafe(board,i-1,j-2)==1) { 
        numofmov++; 
        board[i-1][j-2]++; 
       } 
      } 
     } 
    } 
} 
int main() { 

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     int k; 
     scanf("%d",&k); 
     int board[15][15]; 
     for(int j=0;j<15;j++){ 
      for(int h=0;h<15;h++){ 
       board[j][h]=0; 
      } 
     } 
     for(int i=0;i<k;i++){ 
      int x,y; 
      scanf("%d %d",&x,&y); 
      board[x-1][y-1]++; 
     } 
     int bro=0,mov=numofmov; 
     while(bro==0){ 
      move(board); 
      if(numofmov==mov){ 
       bro++; 
       printf("Second\n"); 
       break; 
      } 
      mov = numofmov; 
      move(board); 
      if(numofmov==mov){ 
       bro++; 
       printf("First\n"); 
       break; 
      } 
      mov = numofmov; 
     } 
    } 
    return 0; 
} 

我的做法是继续做一切可能的行动对所有的硬币,直到我们来到一个点时没有动作是可能的。但是这在一些测试案例中给出了错误的答案。

+6

你的问题,完全靠的链接。链接可能会随着时间的推移而中断,因此最好将相关代码和引号包含到问题中。 – SurvivalMachine

+0

链接有我的代码.....是不是在工作? – yobro97

+0

对不起,我有点快捷。我将你的代码添加到了问题中。我也拿走了'C++'标签,因为它看起来像它的直线'c'。如果你解释你遇到的问题,它会改善你的问题。 –

回答

2

你在问这种方法有什么问题?

“我的做法是继续做所有的动作能对所有 硬币,直到我们来的时候没有动作是可能的一个点。但是,这是 给错误的答案,在一些测试案例。”

我没看过你的代码,但我可以说主要问题是你的方法本身。你正在把这个问题想象成一种蛮力(让所有可能的移动路径,并看看谁赢了)。可能的移动次数可以是任意大的,检查移动导致胜利是无限缓慢的。实际上,它要么是动态编程,要么是更相关的博弈论问题。 这样想一想。起始位置是否唯一标识了此游戏的获胜者?如果我改变一个硬币的初始位置,那么赢家也会改变吗?

解决这类问题的最佳方法是简化它。假设只有一块硬币位于(x,y)。现在请注意,在硬币从位置(x,y)到位置(a,b)每次移动之后,以下为真a+b<x+y。所以如果(x,y)(1,1),(1,2),(2,1),(2,2)其中之一,那么移动的球员已经输了。所以我的目标是要确保我的对手会从已经失去的位置上采取行动,如果我能做到这一点,我就处于胜利的位置。如果你遵循相同的逻辑,你会意识到这种方法将唯一确定位置是赢或输。因此,对于任何头寸,我们都可以回答,如果它正在赢或失,只需从(1,1)(15,15)后退,即可构建答案网格。

现在如果电路板的数量超过一个,你会做什么?您需要深入研究游戏理论,特别是Grundy号码以及它们与Nim游戏的关系。我建议你检查的详细信息,下面的链接:

https://en.wikipedia.org/wiki/Nim

https://en.wikipedia.org/wiki/Nimber

https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/