2016-07-18 3 views
-1

https://www.hackerrank.com/challenges/chessboard-game-again-1チェスボードゲーム...しかし、別の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/

関連する問題