TopCoder, Single Round Match 646, Division 1, Level 2 : TheGridDivOne

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13627&rd=16278

問題概要

　今，無限に広い 2 次元空間の原点にいる．1 回の移動では 4 近傍（いずれかの座標軸に平行な方向）のいずれかの方向に距離 1 移動することができる．
　平面上のいくつかの座標はブロックされていて，その点を通ることはできない．ブロックされている座標の情報は 2 つの配列 で与えられ，各 について， がブロックされている座標である．
　 回以内の移動で到達できる，最も大きな X 座標の値を求めよ．
　
　

解法

　Division 2, Level 2 とほぼ同じ問題設定ですが， の値がかなり大きくなっています．この制約だと，盤面を完全に保持することはできません．
　ここで，盤面の様子について考えてみます．ブロックされている点の数が 47 個以下なので，盤面にはほとんど何も無くて，「スッカスカ」な状態です．また，内部にブロックされた点を含まないような矩形領域について考えると，その内部は自由に移動できます．領域内に始点と終点を定めれば，最小の移動回数は 2 点のマンハッタン距離に等しくなります．このことを踏まえると，ちゃんと考える必要があるのはブロックされている点の周辺だけであることが分かります．従って，座標圧縮して 個程度の座標について考えれば，各点への最小移動回数を求めることができます．この場合は（圧縮後に）隣接する点への移動コストが 1 だけではなくなるので，BFS ではなく Dijkstra 法を用いる必要があります．
　あとは集計だけですが， 回よりも少ない移動回数でたどり着いた点からは，そこから残りの移動回数をすべて使って X 軸正方向へ移動したときの座標で集計する必要があります．

コード

using VI = vector< int >;
using VVI = vector< VI >;
using PII = pair< int, int >;
using VPII = vector< PII >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using LIM = numeric_limits< T >;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

constexpr int INF = LIM<>::max() / 2;
constexpr int dy[] = { 0, 1, 0, -1 };
constexpr int dx[] = { 1, 0, -1, 0 };

class TheGridDivOne
{
public:
	int find( vector <int> x, vector <int> y, int k )
	{
		const int N = SZ( x );

		VPII blocked;
		transform( ALL( y ), x.begin(), BI( blocked ), []( const int a, const int b ){ return MP( a, b ); } );
		sort( ALL( blocked ) );

		const VI ys = compress( y ), xs = compress( x );
		const int H = SZ( ys ), W = SZ( xs );


		using State = tuple< int, int, int >;
		VVI distances( H, VI( W, INF ) );
		priority_queue< State, VT< State >, greater< State > > que;
		{
			const int i = lower_bound( ALL( ys ), 0 ) - ys.begin();
			const int j = lower_bound( ALL( xs ), 0 ) - xs.begin();

			que.EM( distances[i][j] = 0, i, j );
		}

		while ( !que.empty() )
		{
			const int dist = get<0>( que.top() );
			const int cy = get<1>( que.top() );
			const int cx = get<2>( que.top() );
			que.pop();

			if ( distances[ cy ][ cx ] < dist )
			{
				continue;
			}

			const int rcy = ys[ cy ], rcx = xs[ cx ];

			REP( d, 0, 4 )
			{
				const int ny = cy + dy[d], nx = cx + dx[d];
				const int rny = ys[ ny ], rnx = xs[ nx ];

				if ( !( 0 <= ny && ny < H && 0 <= nx && nx < W ) || binary_search( ALL( blocked ), MP( rny, rnx ) ) )
				{
					continue;
				}

				const int cost = abs( rcy - rny ) + abs( rcx - rnx );

				if ( dist + cost < distances[ ny ][ nx ] )
				{
					que.EM( distances[ ny ][ nx ] = dist + cost, ny, nx );
				}
			}
		}
		int res = -INF;
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( k < distances[i][j] )
				{
					continue;
				}

				const int ry = ys[i], rx = xs[j];

				int mx = rx + ( k - distances[i][j] );
				FOR( b, blocked )
				{
					if ( ry == b.fst && rx < b.snd )
					{
						mx = min( mx, b.snd - 1 );
					}
				}

				res = max( res, mx );
			}
		}
		return res;
	}

	VI compress( const VI &as )
	{
		VI res( as );
		res.EB( 0 );

		FOR( a, as )
		{
			res.PB( a - 1 );
			res.PB( a + 1 );
		}
		sort( ALL( res ) );
		res.erase(
				unique( ALL( res ) ),
				res.end() );
		return res;
	}
};