2016-07-18 35 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/