-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;
}

私のアプローチは、移動が不可能になるまで、すべてのコインに対してすべての移動を可能にすることです。しかし、これはいくつかのテストケースで間違った答えを出しています。

4

1 に答える 1

3

このアプローチの何が問題なのかを尋ねていますか?

「私のアプローチは、すべてのコインですべての動きが可能になるまで続けることです。しかし、これはいくつかのテストケースで間違った答えを出しています。」

私はあなたのコードを読んでいませんが、主な問題はあなたのアプローチそのものだと言えます。あなたはこの問題を力ずくで考えています (すべての可能な移動パスを作成し、誰が勝っているかを確認します)。可能な動きの数は任意に大きくなる可能性があり、動きが勝利につながるかどうかのチェックは無限に遅くなります。実際には、それは動的プログラミングの問題か、より関連性の高いゲーム理論の問題です。このように考えてみてください。開始位置は、このゲームの勝者を一意に識別しますか? シングル コインの最初の位置を変更すると、勝者も変更されますか?

この種の問題に取り組む最善の方法は、単純化することです。に配置された 1 枚のコインを持つ 1 つのボードのみがあると仮定し(x,y)ます。(x,y)ここで、コインが位置から位置に移動するたび(a,b)に、次のことが成り立つことに注意してa+b<x+yください。(x,y)が の 1 つである場合(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/

于 2016-07-19T08:18:11.947 に答える