【BZOJ5138】[Usaco2017 Dec]Push a Box（强连通分量）
题面
题解
这题是今天看到萝卜在做然后他一眼秒了，我太菜了不会做，所以就来做做。
首先看完题目，是不是有点像\(NOIP\)的那道华容道？
所以类似的考虑状态\(f[x][y][d]\)，表示当前箱子在\((x,y)\)位置，人在\(d\)(上下左右中的一个)方向时是否存在。那么这样子的状态数是\(4nm\)个，显然是可以的。考虑转移的话就是人推箱子了，沿着某个方向直接推是很容易的，现在的问题是如何让箱子不懂，换个方向。显然，如果箱子不动，人要换个方向的话，那么必定需要存在一条路径可以让人从一个方向走到另外一个方向，而箱子必定阻断了一条路径，所以等价于两个方向所在的点必定在一个点双内。那么把箱子扔掉，考虑所有空位置构成的点双，然后\(bfs\)一遍判断能否达到的所有位置即可。
然后是傻逼yyb调了2h,然而竟然是把一个变量yy写成了y。yyb习惯性连打两个y
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 1555
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,q,dfn[MAX*MAX],low[MAX*MAX],tim,S[MAX*MAX],top,tot,cnt;
int sx,sy,ex,ey,f[MAX][MAX][4];
bool vis[MAX][MAX];
char g[MAX][MAX];
int bh[MAX][MAX];
vector<int> G[MAX*MAX];
int d[4][2]={-1,0,1,0,0,-1,0,1};
struct Node{int x,y,d;};
queue<Node> Q;
void Tarjan(int x,int y,int fx,int fy)
{
dfn[bh[x][y]]=low[bh[x][y]]=++tim;S[++top]=bh[x][y];
for(int i=0;i<4;++i)
{
int xx=x+d[i][0],yy=y+d[i][1];
if(g[xx][yy]=='#')continue;
if(xx==fx&&fy==yy)continue;
if(!dfn[bh[xx][yy]])
{
Tarjan(xx,yy,x,y);
low[bh[x][y]]=min(low[bh[x][y]],low[bh[xx][yy]]);
if(low[bh[xx][yy]]>=dfn[bh[x][y]])
{
++cnt;int v;
do{G[v=S[top--]].push_back(cnt);}while(v!=bh[xx][yy]);
G[bh[x][y]].push_back(cnt);
}
}
else
low[bh[x][y]]=min(low[bh[x][y]],dfn[bh[xx][yy]]);
}
}
void BFS1()
{
Q.push((Node){sx,sy,0});vis[sx][sy]=true;
while(!Q.empty())
{
Node u=Q.front();Q.pop();
for(int i=0;i<4;++i)
{
int x=u.x+d[i][0],y=u.y+d[i][1];
if(g[x][y]=='#')continue;
if(x==ex&&y==ey){f[ex][ey][i^1]=true;continue;}
if(vis[x][y])continue;
vis[x][y]=true;Q.push((Node){x,y,0});
}
}
}
bool check(int a,int b,int x,int y)
{
for(int i=0,l1=G[bh[a][b]].size();i<l1;++i)
for(int j=0,l2=G[bh[x][y]].size();j<l2;++j)
if(G[bh[a][b]][i]==G[bh[x][y]][j])
return true;
return false;
}
void BFS2()
{
for(int i=0;i<4;++i)if(f[ex][ey][i])Q.push((Node){ex,ey,i});
while(!Q.empty())
{
Node u=Q.front();Q.pop();
//1.转到其它方向上面去
for(int i=0;i<4;++i)
{
if(f[u.x][u.y][i])continue;
int x=u.x+d[i][0],y=u.y+d[i][1];
if(g[x][y]=='#')continue;
if(check(u.x+d[u.d][0],u.y+d[u.d][1],x,y))
f[u.x][u.y][i]=true,Q.push((Node){u.x,u.y,i});
}
//2.推一步
int x=u.x+d[u.d^1][0],y=u.y+d[u.d^1][1];
if(g[x][y]!='#')
if(!f[x][y][u.d])
f[x][y][u.d]=true,Q.push((Node){x,y,u.d});
}
}
int main()
{
n=read();m=read();q=read();
memset(g,'#',sizeof(g));
for(int i=1;i<=n;++i)scanf("%s",g[i]+1),g[i][m+1]='#';
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(g[i][j]=='A')sx=i,sy=j,g[i][j]='.';
else if(g[i][j]=='B')ex=i,ey=j,g[i][j]='.';
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(g[i][j]!='#')bh[i][j]=++tot;
Tarjan(sx,sy,0,0);
BFS1();BFS2();
while(q--)
{
int x=read(),y=read();bool fl=(x==ex)&&(y==ey);
for(int i=0;i<4;++i)fl|=f[x][y][i];
puts(fl?"YES":"NO");
}
return 0;
}