SRM580 Div2 Hard 「WallGameDiv2」
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12579
訳
ウサギとウナギはボードゲームで遊んでいる。このゲームはマスが格子状に並んだボードに置かれた1つの駒を使って遊ぶ。セルには駒をそこに置くときにかかるコストを示す数字が書かれている。また、' x 'と書かれたセルは壊れている事を示し、そこに駒を移動する事は出来ない。
初め、駒は一番左の一番上に置かれている。(このセルは壊れていないし、コストは0である事が保障されている)ウナギはゲームを始まると、壁を配置していく。ウナギは壁を好きなだけ置く事ができる。もちろん置かないこともできる。壁は同じ列の隣り合うマスの間に置かなくてはならない。
ウナギが壁を置いたら、ウサギは駒を動かしていく。ウサギは駒を1つ左に、1つ右に、そして1つ下に動かす事ができる。(上に動かす事ができないことに留意せよ)ウサギは壊れていないマスのみに駒を動かす事ができる。ラビットはマスに移動するごとに、そのマスのコストを支払わなくてはならない。
ウサギが一番下のマスのどこかに到達した時点でゲーム終了である。必ず到達できる事は保障されており、ウナギはこの制約を破るように壁を置いてはならない。ゲームは常に終えることができる。
ラビットの目標はゲーム中に支払うコストの最小化であり、ウナギはその最大化である。あなたはマスのコストを表すString[] costsが与えられる。数字であればi番目の文字列のj番目の文字はi行j列のマスのコスト表し、' x 'であればそのマスは壊れている事を表す。ウサギとウナギが最善を尽くしたときにウサギが支払うコストを返せ。
制約
2 <= 行数 <= 50
1 <= 列数 <= 50
考えた事
要は、左右下に動き、一度通ったマスを通らないようしたときの、最大コストを出せってことだ。これはdp[ i ][ j ] = マス( i, j )にきたときの最大コストとして、DPすればよい。初期値はdp[0][0] = 0で他は-1(到達できないことを表す)更新はdp[i+1][x] = dp[i][j] + そこまでかかるコスト。ただしマス( i + 1, x )が壊れてなく、マス( i, j )からマス( i, x )まで移動できる事が条件となる。結果はdp[h-1][x]で最大のものとなる。
事後
初めウナギはマスを壊すもんだと思っててバグッた
ソースコード
class WallGameDiv2 { public: void putMax( int& target, int value ){ target = max( target, value ); } int play(vector <string> costs){ int h = costs.size(); int w = costs[0].length(); // dp初期化 int dp[55][55]; memset( dp, -1, sizeof(dp) ); dp[0][0] = 0; // dp更新 for( int y = 0; y < h - 1; y++ ){ for( int x = 0; x < w; x++ ){ if( dp[y][x] == -1 ) continue; // そのまま下へ if( costs[y+1][x] != 'x' ){ int downCost = costs[y+1][x] - '0'; putMax( dp[y+1][x], dp[y][x] + downCost ); } // 右に動いて下へ int rowCost = 0; for( int nx = x + 1; nx < w && costs[y][nx] != 'x'; nx++ ){ rowCost += costs[y][nx] - '0'; if( costs[y+1][nx] != 'x' ){ int downCost = costs[y+1][nx] - '0'; putMax( dp[y+1][nx], dp[y][x] + rowCost + downCost ); } } // 左に動いて下へ rowCost = 0; for( int nx = x - 1; nx >= 0 && costs[y][nx] != 'x'; nx-- ){ rowCost += costs[y][nx] - '0'; if( costs[y+1][nx] != 'x' ){ int downCost = costs[y+1][nx] - '0'; putMax( dp[y+1][nx], dp[y][x] + rowCost + downCost ); } } } } // 集計 int res = 0; for( int x = 0; x < w; x++ ){ res = max( res, dp[h-1][x] ); } return res; } };