TopCoder SRM 576 Div1 Easy ArcadeManao

問題

hxwのグリッドがある。Xのマスは床で、そこを歩くことができる。
.のマスは床がなくて歩くことができない。

グリッドのh-1行目は全てXで、ここからスタートしてゴールのマスへ移動する。
Xの上ならば左右には自由に動けて、同じ列にあるXには、はしごをかけて移動する。
n行上（または下）のXに移動するには長さnのはしごが必要。

必要なはしごの長さは最小でいくらか。
はしごは何回でも使えるものとする。

制約条件

h, w≦50

方針

最短路を求めるだけ。
ダイクストラ法でも、はしごの長さを固定して幅優先探索でもいい。

ソースコード

class ArcadeManao {
	public:
	int shortestLadder(vector <string> level, int coinRow, int coinColumn) {
		
		int h = level.size(), w = level[0].size();
		
		priority_queue<pi> q;
		set<pi> s;
		
		rep(i, w) q.push(mp(0, (h - 1) * w + i));
		
		while(!q.empty()){
			int co = q.top().first;
			int y = q.top().second / w, x = q.top().second % w;
			q.pop();
			
			if(s.count(mp(y, x))) continue;
			s.insert(mp(y, x));
			if(y == coinRow - 1 && x == coinColumn - 1) return -co;
			
			rep(d, 2){
				int nx = x + (d ? 1 : -1);
				if(nx < 0 || nx >= w || level[y][nx] == '.') continue;
				
				if(!s.count(mp(y, nx)))
				q.push(mp(co, y * w + nx));
			}
			rep(i, h) if(level[i][x] == 'X' && !s.count(mp(i, x)))
			q.push(mp(min(co, -abs(i - y)), i * w + x));
		}
		return -1;
	}
};