自动搬运

查看原文

来自洛谷，原作者为

	Rainybunny / 我是否能成为谁 关于大海的形容 /

搬运于2025-08-24 21:56:17，当前版本为作者最后更新于2019-07-16 20:28:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

请问dalao们圆方树是什么...
于是, 不妨来想一些简单的操作吧.

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

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

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

3. 反之, 则$A$与$B$由至少两条路径$P=<A,v_1,v_2,...,B>$, $P'=<A,v_1',v_2',...,B>$相连, 且满足$P\bigcap P'=\lbrace A,B\rbrace$. 所以$A$, $B$一定隶属于同一个点双.

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

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

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

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

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

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

• 有的小朋友为了方便判断有无相同的点双编号, 会选择使用$set$等$STL$储存每个点所隶属的点双编号, $T$掉一大半, 开$O2$就能$A$. STL极欠调教啊/滑稽.

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

• 多检查几遍那该死的$Tarjan$, 我帮几个老铁调, 全是Tarjan错/再次滑稽.

好了, 上代码吧. 有详细注释哦!

#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 } };
// Move[0..3]分别对应上, 左, 下, 右 
int n, m, q, px, py, bx, by, PDCC, InCpr[MAXN + 5][MAXN + 5][5] = {};
// n, m, q为输入, (px,px)为人物起始坐标, (bx,by)为箱子起始坐标, PDCC为点双数量, InCpr[i][j]为结点隶属信息, 其中InCpr[i][j][0]为隶属个数 
int Indx, DFN[MAXN + 5][MAXN + 5] = {}, Low[MAXN + 5][MAXN + 5] = {};
// Tarjan的一堆东西 
bool Up, Left, Down, Right, Vis[MAXN + 5][MAXN + 5][4] = {}, B_vis[MAXN + 5][MAXN + 5] = {};
// 四个方向能否到达, 以及两个BFS的Vis数组 ( 栈空间开不下 ) 
char Map[MAXN + 5][MAXN + 5] = {};
// 地图 
stack<pair<int, int> > S;
// Tarjan的栈 

struct Node { // BFS结点 
	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 ) { // 万恶之源Tarjan 
	DFN[x][y] = Low[x][y] = ++ Indx; // 这里可以选择将坐标Hash 
	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 ) { // 贴近box(预处理) 
	queue<pair<int, int> > Q;
	Q.push ( make_pair ( x, y ) );
	B_vis[x][y] = true;
	while ( ! Q.empty () ) { // 这个xjb乱搜就行了, 问题不大 
		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' ) { // 判' '与'\n' 
				-- 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] ) { // 这里需要注意, #3的坑点, 人物本来就无法靠近箱子, 特判掉 
		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 () {
//	freopen ( "pushbox.in", "r", stdin );
//	freopen ( "pushbox.out", "w", stdout );
	Work ();
	return 0;
}

感谢您的阅读. 或许是copy代码呢!