WARush

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

SRM583 Div2 Hard "GameOnABoard"

問題

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

アリスとボブはボードゲームで遊んでいる。これから出てくる(i, j)と言う表記はi行のj列(0-base)のマスを意味する。それぞれのマスには0か1どちらかのコストが設定されており、それはString[] cost として与えられる。costのi番目の文字列のj番目の文字は、(i, j)のコストを表している。(x1, y1)と(x2, y2)の異なるマスの経路とはc0 = (x1, y1), ck = (x2, y2)であるマスのシーケンス(c0, c1, ..., ck)で表され、c_iとc_i+1は共通の辺を持ったマス同士である必要がある。経路のコストは含まれるマスのコストの合計となる。

このゲームは次のようにして遊ぶ・・まずアリスがマス(x1, y1)を選び、それからボブがアリスが選んだのとは異なるマス(x2, y2)を選ぶ。最後に(x1, y1) - (x2, y2)の経路の最小のコスト L を計算する。アリスの目的はLを最小化することであり、ボブの目的はLを最大化することである。2人が最善を尽くすしたときの、Lの値を返せ。

制約

ボードの最大の大きさ = 40 * 40



考えたこと

ボブが後攻なので、選んだスタート地点からコストが最大となるゴールを選ばれるのは避けられない。よって、各スタート地点からの最大のコストを計算し、それの最小をとっていけばよい。



ソースコード

int H, W;
vector<string> cost;


class GameOnABoard {
public:

    int solve( int x, int y ){
        // x, yからダイクストラ
        // 始点のコストを考慮する
        int scost = cost[y][x] - '0';
        int d[2550];
        for( int i = 0; i < H; i++ ){
            for( int j = 0; j < W; j++ ){
                int id = i * W + j;
                if( i == y && j == x ){
                    d[id] = scost;
                }else{
                    d[id] = 2550;
                }
            }
        }

        priority_queue<pair<int, int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
        que.push( make_pair( scost, y * W + x ) );
        while( !que.empty() ){
            // 一番よいものを取り出す
            int co = que.top().first;
            int id   = que.top().second;
            que.pop();

            // 陳腐化してたら何もしない
            if( d[id] < co ) continue;

            int y = id / W;
            int x = id % W;

            int dx[] = { 0, 0, -1, 1 };
            int dy[] = { -1, 1, 0, 0 };
            // 上下左右を調べる
            for( int i = 0; i < 4; i++ ){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if( nx < 0 || W <= nx || ny < 0 || H <= ny ) continue;
                int nid = ny * W + nx;
                int ncost = co + (cost[ny][nx] == '1' ? 1 : 0);
                // 更新できたらキューに入れる
                if( ncost < d[nid] ){
                    d[nid] = ncost;
                    que.push( make_pair( ncost, nid ) );
                }
            }
        }

        // 最大値を返す
        int res = 0;
        for( int i = 0; i < H * W; i++ ){
            res = max( res, d[i] );
        }
        return res;
    }


    int optimalChoice(vector <string> _cost){
        H = _cost.size();
        W = _cost[0].length();
        cost = _cost;

        int ans = 2550;
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                ans = min( ans, solve( x, y ) );
            }
        }

        return ans;
    }
};