問題概要
今,無限に広い 2 次元空間の原点にいる.1 回の移動では 4 近傍(上下左右)のいずれかの方向に距離 1 移動することができる.
平面上のいくつかの座標はブロックされていて,その点を通ることはできない.ブロックされている座標の情報は 2 つの配列 で与えられ,各 について, がブロックされている座標である.
回以内の移動で到達できる,最も大きな X 座標の値を求めよ.
解法
到達できる点の,原点からのマンハッタン距離は 以下です. の制約を考えると, ぐらいの矩形領域についてだけ考えれば,到達可能な点を全て考慮できることが分かります.このサイズはさほど大きくないので,普通に BFS をすることで,各点へ到達するための最小移動回数を求めることができます.あとは, 回以内の移動で到達できる点の内,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; } };