WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM588 Div2 Hard "GameInDarknessDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12710

アリスとボブは四角いボードを使ったゲームで遊んでいる。行と列には、両方とも0から始まる番号がつけられている。これより、i番目の列、j番目の行のマスを( i, j )と表す。マス( 0, 0 )とは左上の隅のマスの事である。ボードは壁マスと空マスで構成されており、このゲームは空マスだけを使って遊ぶ。

ゲームは以下のようにして遊ぶ。ボード上には、アリスとボブの駒が、1つずつ置かれている。ゲーム開始当初、その2つの駒が同じマスに置かれている事はない。プレイヤーは交互に駒を動かしていく。初めに動かすのはアリスである。駒は、現在のマスの隣り合うマスに動かしていく。(壁マスには動かす事はできない)なお、手番が回ってきたら、駒は必ず動かす必要があり、その場に留まることはできない。

2つの駒が、同じマスに到達すれば、アリスの勝ちである。もし、アリスが(下記で説明するように)ギブアップしたらボブの勝ちである。

あなたはボードの状態を示す、Stringの配列 fieldが与えられる。field[i][j]はマス( i, j )に対応しており、それが'.'であれば空マス、'#'であれば壁マスであることを示す。また、'A'はアリスの駒の初期位置で、'B'はボブの駒の初期位置である。当然ながら、'A' 'B' のマスは壁マスではなく、空マスである。

このゲームはちょっと変わっていて、ボードは完全に闇に包まれているのである。アリスとボブはお互いに初期位置は分かっている。アリスはボブの現在の位置を知るすべはない。しかし、ボブはアリスがこのゲームでどう動いてくるのかを正確に把握している。

あなたはStringの配列 movesが与えられる。これはアリスが行うであろう駒の動かし方を示す。movesの全ての要素を連結した文字列をMとする。M[i-1]は、アリスのiターン目に対応しており、その文字によって、アリスは下記のように駒を動かしてくる。

'U' : 上に動かす
'D' : 下に動かす
'L' : 左に動かす
'R' : 右に動かす

この情報では、アリスは壁に向かって進んだり、ボードをはみ出したりせず、空のマスを移動する事が保証される。アリスがMの文字を使い切ってもボブを捕えきれない場合、アリスはギブアップし、ボブの勝利となる。

ボブが最善を尽くしたときに、ボブが勝つのならば"Bob wins"を、そうでなければ"Alice wins"を返せ。

制約

1 <= マスの行・列 <= 50
1 <= アリスの行動回数 <= 2500



考えた事

DP[ボブのx位置][ボブのy位置][ターン数]のdpでいける。

ボブの進む先に、アリスがいてはいけない。また、ボブの動き出し時、アリスと同じマスにいてはいけない。



ソースコード

int N;
int H, W;
vector<string> F;
int xs[2550], ys[2550]; // iターン時のアリスの位置
int memo[55][55][2550];


// tターン目に(x, y)に居たときBobは逃げ切れるか?
bool dfs( int x, int y, int t ){

    if( memo[x][y][t] != -1 ){
        return memo[x][y][t] == 1;
    }

    bool res = false;

    // ターンを越してたら勝ち
    if( N < t ){
        res =  true;
    }
    // Aliceが同じマスにいたら負け
    else if( x == xs[t+1] && y == ys[t+1] ){
        res = false;
    }
    // 上下左右試す
    else{
        int dx[] = { 0, 0, -1, 1 };
        int dy[] = { -1, 1, 0, 0 };

        for( int d = 0; d < 4; d++ ){
            int nx = x + dx[d];
            int ny = y + dy[d];
            // フィールドからはみ出してない?
            if( nx < 0 || W <= nx || ny < 0 || H <= ny ) continue;
            // そこ壁じゃない?
            if( F[ny][nx] == '#' ) continue;
            // そこにAliceいない?
            if( nx == xs[t+1] && ny == ys[t+1] ) continue;
            // 移動を試みる
            res |= dfs( nx, ny, t + 1 );
        }
    }

    // メモ
    memo[x][y][t] = res ? 1 : 0;
    
    return res;
}


class GameInDarknessDiv2 {
public:
    string check(vector <string> field, vector <string> moves){
        string move;
        for( int i = 0; i < moves.size(); i++ ){
            move += moves[i];
        }
        N = move.length();

        H = field.size();
        W = field[0].length();
        F = field;

        // 初期位置取得
        int ax, ay, bx, by;
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( F[y][x] == 'A' ){
                    ax = x; ay = y;
                }
                if( F[y][x] == 'B' ){
                    bx = x; by = y;
                }
            }
        }

        // xs, ys初期化
        xs[0] = ax; ys[0] = ay;
        for( int i = 1; i <= N; i++ ){
            int dx = 0, dy = 0;
            if( move[i-1] == 'U' ){
                dy = -1;
            }
            if( move[i-1] == 'D' ){
                dy = 1;
            }
            if( move[i-1] == 'L' ){
                dx = -1;
            }
            if( move[i-1] == 'R' ){
                dx = 1;
            }

            xs[i] = xs[i-1] + dx;
            ys[i] = ys[i-1] + dy;
        }

        // dfs
        memset( memo, -1, sizeof(memo) );
        bool bobwin = dfs( bx, by, 0 );

        return bobwin ? "Bob wins" : "Alice wins";
    }
};