题解 P4082 【[USACO17DEC]Push a Box】
Rainybunny
·
·
题解
请问dalao们圆方树是什么...
于是, 不妨来想一些简单的操作吧.
本题的难点是, 移动的箱子造成了地图的不断变化, 箱子所在的点会成为障碍, 可能导致一些本能走到的位置不再相连...这不是割点吗?!
在无向连通图中, 对于割点的定义是: 若删去该点及其连边, 图不再连通. 所以我们可以试着强行用Tarjan跑出地图上所有割点的坐标, 顺便取得每个点所隶属的点双连通分量编号 ( 所以, 割点应该隶属于多个点双 ), 接下来我们讨论如何快速判断能否从某个方向推动箱子, 假设现有状态"A-box-B" ( 具体来说, 设有两个位置A, B与箱子box相邻 ):
-
首先由题意, 在不考虑box的阻挡时, A与B应当由一条经过box位置的路径相连.
-
若考虑box的阻挡, A与B不再相通, 则由论述1. A, B之间有且仅有一条经过box位置的路径相连. 那么由割点的定义, box的位置是割点, A, B一定不属于同一个点双.
-
反之, 则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隶属于同一个点双.
剩下的一切好说. 我就调了俩小时. 所以我们再捋一捋代码:
-
-
-
- 有的小朋友为了方便判断有无相同的点双编号, 会选择使用$set$等$STL$储存每个点所隶属的点双编号, $T$掉一大半, 开$O2$就能$A$. ~~STL极欠调教啊/滑稽~~.
- 关于最终的$BFS$如何储存状态, 定义$Vis[i][j][k]$表示箱子在$(i,j)$, 人物在箱子的$k$方向即可.
- 多检查几遍~~那该死的~~$Tarjan$, ~~我帮几个老铁调, 全是Tarjan错/再次滑稽~~.
好了, 上代码吧. 有详细注释哦!
```cpp
#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代码呢!~~