torus711 のアレ

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

TopCoder, Single Round Match 646, Division 2, Level 2 : TheGridDivTwo

問題概要

 今,無限に広い 2 次元空間の原点にいる.1 回の移動では 4 近傍(上下左右)のいずれかの方向に距離 1 移動することができる.
 平面上のいくつかの座標はブロックされていて,その点を通ることはできない.ブロックされている座標の情報は 2 つの配列 x, y で与えられ,各 i について,( x_i, y_i ) がブロックされている座標である.
 k 回以内の移動で到達できる,最も大きな X 座標の値を求めよ.
 k \leq 1000

解法

 到達できる点の,原点からのマンハッタン距離は k 以下です.k の制約を考えると,2000 \times 2000 ぐらいの矩形領域についてだけ考えれば,到達可能な点を全て考慮できることが分かります.このサイズはさほど大きくないので,普通に BFS をすることで,各点へ到達するための最小移動回数を求めることができます.あとは,k 回以内の移動で到達できる点の内,X 座標最大のものを求めれば,答えを得られます.
 以下のコードでは,BFS と同時に集計も行っています.

コード

using PII = pair< int, int >;
template < typename T = int > using LIM = numeric_limits< T >;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )

#define SZ( v ) ( (int)( v ).size() )
#define EM emplace

#define fst first
#define snd second

constexpr int INF = LIM<>::max() / 2;
constexpr int OFFSET = 1024;

constexpr int dy[] = { 0, 1, 0, -1 };
constexpr int dx[] = { 1, 0, -1, 0 };

int distances[ 2048 ][ 2048 ], blocked[ 2048 ][ 2048 ];

class TheGridDivTwo
{
public:
	int find( vector <int> x, vector <int> y, int k )
	{
		{ // initialize for local test
			fill( AALL( blocked, int ), 0 );
		}

		transform( ALL( x ), x.begin(), bind( plus< int >(), _1, OFFSET ) );
		transform( ALL( y ), y.begin(), bind( plus< int >(), _1, OFFSET ) );

		REP( i, 0, SZ( x ) )
		{
			blocked[ y[i] ][ x[i] ] = 1;
		}

		fill( AALL( distances, int ), INF );
		distances[ OFFSET ][ OFFSET ] = 0;

		queue< PII > que;
		que.EM( OFFSET, OFFSET );

		int res = 0;
		
		while ( !que.empty() )
		{
			const int cy = que.front().fst;
			const int cx = que.front().snd;
			que.pop();

			res = max( res, cx - OFFSET );

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

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

				if ( !blocked[ ny ][ nx ] && distances[ cy ][ cx ] + 1 < distances[ ny ][ nx ] )
				{
					distances[ ny ][ nx ] = distances[ cy ][ cx] + 1;
					que.EM( ny, nx );
				}
			}
		}

		return res;
	}
};