SRM576 Div1 Easy, Div2 Medium "ArcadeManao"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12504
訳
昔こんなゲームがあった。
そのゲームはN * Mマスのマップで構成されている。
いくつかのマスはその上に立つことができるようになっている(地面マス)。
一番下の列は全てそのようなマスで、地面になっている。
列は上から1~N、行は左から1~Mの番号が振られている。
そして、ただ1つのセルにプレイヤーの目標としているコインが置いてある。
(マリオみたいなもんですかね、問題にイメージ図もあります)
最初、プレイヤーはマップの一番下の地面マスに立っている。
彼は水平に隣り合う2つの地面マスを移動する事ができる。
さらに、はしごを使って上下の地面マスに移動する事もできる。
そのはしごの長さがLだったとすると、彼は|i1 - i2| <= L であるような、
(i1, j), (i2, j)の地面マスを上り下りする事ができる。
プレイヤーははしごを複数回使うことができる。
マップの情報(地面マス、コインの位置)が与えられるので、
コインを取るために最低限必要な、はしごの長さを返せ。
制約
1 <= N, M <= 50
考えた事
地面マスを頂点としたグラフを作り、
ダイクストラ法で必要最小限のコストを出す。
隣り合う地面マスはコスト0の辺で
上下に位置する地面マス同士は、その距離のコストの辺で結ぶ。
ってやってみたけど、複雑にしてしまった感が・・・
他の人のソースコードをみると、
はしごの長さをまず決めてしまい(0~50)
それぞれの長さでコインの場所から地面に
到達できるかをBFSで判断していた。
こっちのほうが簡単に実装できるなぁ
ソースコード
struct Edge{ int to, cost; }; vector<Edge> G[2550]; int d[2550]; class ArcadeManao { public: int shortestLadder(vector <string> level, int coinRow, int coinColumn){ int H = level.size(); int W = level[0].length(); for( int i = 0; i < 2550; i++ ){ G[i].clear(); } for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( level[y][x] == '.' ) continue; // 右にあったら右に0を張る if( x + 1 < W && level[y][x+1] == 'X' ){ Edge e1 = { y*W+x+1, 0 }; G[y*W+x].push_back(e1); Edge e2 = { y*W+x, 0 }; G[y*W+x+1].push_back(e2); } // 下にあったらその距離だけ張る int y2 = y + 1; while( y2 < H && level[y2][x] == '.' ){ y2++; } if( y2 < H ){ int len = abs( y - y2 ); Edge e1 = { y2*W+x, len }; G[y*W+x].push_back(e1); Edge e2 = { y*W+x, len }; G[y2*W+x].push_back(e2); } } } // ダイクストラ priority_queue < pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que; int s = coinRow*W+coinColumn; que.push( make_pair( 0, s ) ); fill( d, d+2550, 100 ); d[s] = 0; while( !que.empty() ){ pair<int,int> p = que.top(); que.pop(); int v = p.second; if( d[v] < p.first) continue; int n = G[v].size(); for( int i = 0; i < n; i++ ){ Edge e = G[v][i]; // 今までかかっていたコストと、 // 新たにかかるコストの最大をとっていく if( max(e.cost, p.first) < d[e.to] ){ d[e.to] = max(e.cost, p.first); que.push( make_pair(d[e.to], e.to ) ); } } } return d[(H-1)*W]; } };