torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 576, Division 1, Level 1 : ArcadeManao

概要

N \times M の二次元のマップを採用したゲームをする。
マップは、何もないか足場があるかのどちらかであり、マップ中に一つだけコインがある。
横に繋がっている足場にはそのまま移動できる。
縦方向へは、ハシゴを使うことで移動することができる。
ハシゴは持ち歩くことができるので、何度でも使ってよい。
マップの一番下は全て足場になっており、プレイヤーは最初この高さにいる。
コインのある位置まで移動するために必要なハシゴの長さの最小値を求めよ。

解法

各足場へ移動するために必要な最短のハシゴの長さを短い方から順に( Dijkstra 法のように)求めていくと解けます。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define ALL( c ) (c).begin(), (c).end()

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

class ArcadeManao
{
public:
	int shortestLadder( vector <string> level, int coinRow, int coinColumn )
	{
		const int H = level.size(), W = level[0].size();
		coinRow--;
		coinColumn--;

		VVI distance( H, VI( W, INT_MAX ) );
		fill( ALL( distance.back() ), 0 );

		priority_queue< pair<int,PII>, vector< pair<int,PII> >, greater< pair<int,PII> > > que;
		que.push( MP( 0, MP( H - 1, 0 ) ) );
		
		while ( !que.empty() )
		{
			int dist = que.top().fst;
			PII pos = que.top().snd;
			que.pop();

			REP( ix, 0, W )
			{
				if ( distance[ pos.fst ][ ix ] != dist )
				{
					continue;
				}

				REP( iy, 0, H )
				{
					int nextDist = max( dist, abs( iy - pos.fst ) );
					if ( level[ iy ][ ix ] != 'X' || distance[ iy ][ ix ] <= nextDist )
					{
						continue;
					}
					que.push( MP( nextDist, MP( iy, ix ) ) );
					fillHorizontal( level, distance, nextDist, iy, ix );
				}
			}
		}

		return distance[ coinRow ][ coinColumn ];
	}

	void fillHorizontal( const VS &level, VVI &distance, int dist, int y, int x )
	{
		if ( x < 0 || level[0].size() <= x || level[y][x] != 'X' || distance[y][x] <= dist )
		{
			return;
		}
		distance[y][x] = dist;
		fillHorizontal( level, distance, dist, y, x - 1 );
		fillHorizontal( level, distance, dist, y, x + 1 );
		return;
	}
};