题解——割点

本题的难点是, 移动的箱子造成了地图的不断变化, 箱子所在的点会成为障碍, 可能导致一些本能走到的位置不再相连...这不是割点吗?!
在无向连通图中, 对于割点的定义是: 若删去该点及其连边, 图不再连通. 所以我们可以试着强行用Tarjan跑出地图上所有割点的坐标, 顺便取得每个点所隶属的点双连通分量编号 ( 所以, 割点应该隶属于多个点双 ), 接下来我们讨论如何快速判断能否从某个方向推动箱子, 假设现有状态"A−box−B" ( 具体来说, 设有两个位置A, B与箱子box相邻 ):

首先由题意, 在不考虑box的阻挡时, A与B应当由一条经过box位置的路径相连.

若考虑box的阻挡, A与B不再相通, 则由论述1. A, B之间有且仅有一条经过box位置的路径相连. 那么由割点的定义, box的位置是割点, A, B一定不属于同一个点双.

于是得出结论:
A在box的阻挡下能到达B⟺A, B隶属于同一个点双.

剩下的一切好说. 我就调了俩小时. 所以我们再捋一捋代码:

Tarjan, 求出每个点隶属的 ( 一个或多个 ) 点双编号.

BFS/DFS, 预处理, 尝试让人物靠近箱子的四个方向, 并保存能到达的方向.

BFS, 利用上述判别方法, 标记每个箱子能到达的位置.

emmm再好心地说一下细节问题吧:

有的小朋友为了方便判断有无相同的点双编号, 会选择使用set等STL储存每个点所隶属的点双编号, T掉一大半, 开O2就能A。

关于最终的BFS如何储存状态, 定义Vis[i][j][k]表示箱子在(i,j), 人物在箱子的k方向即可.

好了, 上代码吧

#include <queue>
#include <stack>
#include <cstdio>

#define Int register int

using namespace std;

const int MAXN = 1500, Move[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
int n, m, q, px, py, bx, by, PDCC, InCpr[MAXN + 5][MAXN + 5][5] = {};
int Indx, DFN[MAXN + 5][MAXN + 5] = {}, Low[MAXN + 5][MAXN + 5] = {};
 
bool Up, Left, Down, Right, Vis[MAXN + 5][MAXN + 5][4] = {}, B_vis[MAXN + 5][MAXN + 5] = {};

char Map[MAXN + 5][MAXN + 5] = {};

stack<pair<int, int> > S;


struct Node { 
	int px, py, bx, by;
};

inline bool Inside ( const int x, const int y ) { 
	return 1 <= x && x <= n
		&& 1 <= y && y <= m;
}

inline void AddNear ( const int x, const int y, const int NearCprID ) { 
	InCpr[x][y][++ InCpr[x][y][0]] = NearCprID;
}

inline void Tarjan ( const int x, const int y, const int fax, const int fay ) { 
	DFN[x][y] = Low[x][y] = ++ Indx;  
	S.push ( make_pair ( x, y ) );
	for ( Int i = 0; i < 4; ++ i ) {
		int nx = x + Move[i][0], ny = y + Move[i][1];
		if ( Inside ( nx, ny ) && Map[nx][ny] ^ '#' ) {
			if ( ! DFN[nx][ny] ) {
				Tarjan ( nx, ny, x, y );
				if ( Low[nx][ny] >= DFN[x][y] ) {
					++ PDCC;
					AddNear ( x, y, PDCC );
					while ( S.top ().first ^ nx || S.top ().second ^ ny ) {
						AddNear ( S.top ().first, S.top ().second, PDCC );
						S.pop ();
					}
					AddNear ( nx, ny, PDCC );
					S.pop ();
				}
				Low[x][y] = min ( Low[x][y], Low[nx][ny] );
			} else if ( DFN[x][y] > DFN[nx][ny] && ( nx ^ fax || ny ^ fay ) ) {
				Low[x][y] = min ( Low[x][y], DFN[nx][ny] );
			}
		}
	}
}

inline void Beclose ( const int x, const int y, const int Boxx, const int Boxy ) { 
	queue<pair<int, int> > Q;
	Q.push ( make_pair ( x, y ) );
	B_vis[x][y] = true;
	while ( ! Q.empty () ) {
		pair<int, int> p = Q.front ();
		Q.pop ();
		if ( p.first == Boxx - 1 && p.second == Boxy ) Up = true;
		if ( p.first == Boxx && p.second == Boxy - 1 ) Left = true;
		if ( p.first == Boxx + 1 && p.second == Boxy ) Down = true;
		if ( p.first == Boxx && p.second == Boxy + 1 ) Right = true;
		if ( Up && Left && Down && Right ) return ;
		for ( Int i = 0; i < 4; ++ i ) {
			int nx = p.first + Move[i][0], ny = p.second + Move[i][1];
			if ( Inside ( nx, ny ) && Map[nx][ny] ^ '#' && Map[nx][ny] ^ 'B' && ! B_vis[nx][ny] ) {
				B_vis[nx][ny] = true;
				Q.push ( make_pair ( nx, ny ) );
			}
		}
	}
}

inline bool InSameCpr ( const int s, const int t, const int p, const int q ) { 
	for ( Int i = 1; i <= InCpr[s][t][0]; ++ i ) {
		for ( Int j = 1; j <= InCpr[p][q][0]; ++ j ) {
			if ( InCpr[s][t][i] == InCpr[p][q][j] ) {
				return true;
			}
		}
	}
	return false;
}

inline void BFS () {
	queue<Node> Q;
	if ( Up ) Q.push ( Node { bx - 1, by, bx, by } ), Vis[bx][by][0] = true;  
	if ( Left ) Q.push ( Node { bx, by - 1, bx, by } ), Vis[bx][by][1] = true;
	if ( Down ) Q.push ( Node { bx + 1, by, bx, by } ), Vis[bx][by][2] = true;
	if ( Right ) Q.push ( Node { bx, by + 1, bx, by } ), Vis[bx][by][3] = true;
	while ( ! Q.empty () ) {
		Node p = Q.front ();
		Q.pop ();
		for ( Int i = 0; i < 4; ++ i ) {
			int nbx = p.bx + Move[i][0], nby = p.by + Move[i][1];
			int bkx = p.bx + Move[i ^ 2][0], bky = p.by + Move[i ^ 2][1];
			if ( Inside ( nbx, nby ) && Map[nbx][nby] ^ '#' && ( ( bkx == p.px && bky == p.py ) || InSameCpr ( p.px, p.py, bkx, bky ) ) && ! Vis[nbx][nby][i ^ 2] ) {
				Vis[nbx][nby][i ^ 2] = true;
				Q.push ( Node { p.bx, p.by, nbx, nby } );
			}
		}
	}
}

inline void Work () {
	scanf ( "%d %d %d", &n, &m, &q );
	for ( Int i = 1; i <= n; ++ i ) {
		for ( Int j = 1; j <= m; ++ j ) {
			char s = getchar ();
			if ( s ^ '.' && s ^ '#' && s ^ 'A' && s ^ 'B' ) { 
				-- j; continue;
			}
			if ( s == 'A' ) px = i, py = j;
			if ( s == 'B' ) bx = i, by = j;
			Map[i][j] = s;
		}
	}
	Tarjan ( px, py, 0, 0 );
	if ( ! DFN[bx][by] ) { 
		while ( q -- ) {
			int x, y;
			scanf ( "%d %d", &x, &y );
			puts ( x == bx && y == by ? "YES" : "NO" );
		}
		return ;
	}
	Beclose ( px, py, bx, by );
	BFS ();
	while ( q -- ) {
		int x, y;
		scanf ( "%d %d", &x, &y );
		puts ( Vis[x][y][0] || Vis[x][y][1] || Vis[x][y][2] || Vis[x][y][3] ? "YES" : "NO" ); 
	}
}

int main () {
	Work ();
	return 0;
}