WARush

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

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