https://www.zybuluo.com/ysner/note/1293166
题面
解析
挺不错的一道图论码量题。
可以借此回顾一下\(noip2013\)华容道。
思路和华容道差不多。
照洛谷数据规模看，暴搜可能有\(\frac{1}{3}\)的分数。。。
设\(f[w][i][j]\)表示箱子在点\((i,j)\)时，人能否到达\(w\)方向（即\(0/1/2/3\)，表示上下左右）。
那么我们可以先从人出发\(BFS\)一遍，预处理出未推箱子时的\(f[w][i][j]\)。
注意箱子所在点是可以多次更新的。
然后开始推箱子，每次有两种决策：
- 换个方向
- 照原方向推一格
决策可不可行肯定要预处理出来，毕竟\(n\)是\(10^6\)级别的。
显然如果能换方向，就说明换方向的前后两点在同一点双联通分量中。
这玩意儿从人的出发点跑一遍\(Tarjan\)就能预处理出来。
推一格这个操作可以直接转移。
注意边界都要赋为\(\#\)。（尤其是每行末尾）
细节挺多，蒟蒻调了两个多小时。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
#define re register
#define il inline
#define pb(a) push_back(a)
#define gc() getchar()
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1644;
int n,m,q,sx,sy,rx,ry,dfn[N*N],low[N*N],top,sta[N*N],tot,Id[N][N];
int mx[4]={1,-1,0,0},my[4]={0,0,1,-1};
bool f[4][N][N],vis[N][N];
char mp[N][N];
struct dat{int x,y,w;};
queue<dat>Q;
vector<int>c[N*N];
il int id(re int x,re int y){return Id[x][y];}
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=gc();
if(ch=='-') t=-1,ch=gc();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=gc();
return x*t;
}
il void Tarjan(re int x,re int y,re int fx,re int fy)
{
re int u=id(x,y);
sta[++top]=u,dfn[u]=low[u]=++tot;
fp(i,0,3)
{
re int xx=x+mx[i],yy=y+my[i],v=id(xx,yy);
if(mp[xx][yy]=='#') continue;
if(xx==fx&&yy==fy) continue;
if(!dfn[v])
{
Tarjan(xx,yy,x,y);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++tot;re int g;
do{g=sta[top--];c[g].pb(tot);}while(g^v);
c[u].pb(tot);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
il void BFS1()
{
Q.push((dat){rx,ry,0});vis[rx][ry]=1;
while(!Q.empty())
{
re int x=Q.front().x,y=Q.front().y,u=id(x,y);Q.pop();
fp(i,0,3)
{
re int xx=x+mx[i],yy=y+my[i],v=id(xx,yy);
if(mp[xx][yy]=='#'||vis[xx][yy]) continue;
if(xx==sx&&yy==sy) {f[i^1][xx][yy]=1;continue;}
vis[xx][yy]=1;Q.push((dat){xx,yy,0});
}
}
}
il int check(re int x,re int y,re int xx,re int yy)
{
re int u=id(x,y),v=id(xx,yy);
for(re int i=0;i<c[u].size();++i)
for(re int j=0;j<c[v].size();++j)
if(c[u][i]==c[v][j]) return 1;
return 0;
}
il void BFS2()
{
fp(i,0,3) if(f[i][sx][sy]) Q.push((dat){sx,sy,i});
while(!Q.empty())
{
re int x=Q.front().x,y=Q.front().y,w=Q.front().w,u=id(x,y);Q.pop();
fp(i,0,3)
{
if(f[i][x][y]) continue;
re int xx=x+mx[i],yy=y+my[i];
if(mp[xx][yy]=='#') continue;
if(check(x+mx[w],y+my[w],xx,yy)) f[i][x][y]=1,Q.push((dat){x,y,i});
}
{
re int xx=x+mx[w^1],yy=y+my[w^1];///yy=y+mx???????
if(mp[xx][yy]=='#') continue;
if(!f[w][xx][yy]) f[w][xx][yy]=1,Q.push((dat){xx,yy,w});
}
}
}
int main()
{
n=gi();m=gi();q=gi();
memset(mp,'#',sizeof(mp));
fp(i,1,n) scanf("%s",mp[i]+1),mp[i][m+1]='#';
fp(i,1,n)
fp(j,1,m)
{
if(mp[i][j]=='A') rx=i,ry=j,mp[i][j]='.';
else if(mp[i][j]=='B') sx=i,sy=j,mp[i][j]='.';
Id[i][j]=(i-1)*m+j;
}
Tarjan(rx,ry,0,0);
BFS1();
BFS2();
while(q--)
{
re int x=gi(),y=gi(),tag=(sx==x&&sy==y);
fp(i,0,3) tag|=f[i][x][y];
puts(tag?"YES":"NO");
}
return 0;
}