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