P4082 [USACO17DEC]Push a Box P
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int begin_a,begin_b,end_a,end_b;
int deep,tp,cnt;
int dfn[2250020],low[2250020];
int _stack[2250020];
vector <int> G[2250020];
vector <int> T[4500020];
char c[1520][1520];
string s;
bool p[1520][1520][4];
bool dis[1520][1520];
int fa[4500020];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int read()
{
char ch=getchar();
int s=0,w=1;
while (ch<'0'||ch>'9')
{
if (ch=='-')
{
w=-1;
}
ch=getchar();
}
while (ch>='0'&&ch<='9')
{
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
int tra(int x,int y)
{
return (x-1)*m+y;
}
int bk1(int x)
{
return (x-1)/m+1;
}
int bk2(int x)
{
int y=(x-1)/m+1;
return x-(y-1)*m;
}
void dfs(int u,int f)
{
fa[u]=f;
for (int i=0;i<T[u].size();i++)
{
if (T[u][i]!=f)
{
dfs(T[u][i],u);
}
}
return;
}
void CST(int u)
{
dfn[u]=low[u]=++deep;
_stack[++tp]=u;
for (int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if (dfn[v]==0)
{
CST(v);
low[u]=min(low[u],low[v]);
if (low[v]==dfn[u])
{
++cnt;
for (int j=0;j!=v;--tp)
{
j=_stack[tp];
T[cnt].push_back(j);
T[j].push_back(cnt);
}
T[cnt].push_back(u);
T[u].push_back(cnt);
}
}
else
{
low[u]=min(low[u],dfn[v]);
}
}
return;
}
void BFS(int x,int y)
{
queue<int> q;
q.push(tra(x,y));
dis[x][y]=1;
while (!q.empty())
{
int u=bk1(q.front()),v=bk2(q.front());
q.pop();
for (int i=0;i<4;i++)
{
int a=u+dx[i],b=v+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&c[a][b]=='.'&&!dis[a][b])
{
dis[a][b]=1;
q.push(tra(a,b));
}
}
}
}
bool check(int x,int y,int z)
{
if (fa[x]==fa[y]) return 1;
if (fa[fa[x]]==z&&fa[fa[y]]==z) return 0;
if (fa[fa[x]]==z&&fa[fa[z]]==y) return 0;
if (fa[fa[z]]==x&&fa[fa[y]]==z) return 0;
if (fa[fa[z]]==fa[fa[x]]&&fa[fa[y]]==z) return 0;
if (fa[fa[z]]==fa[fa[y]]&&fa[fa[x]]==z) return 0;
return 1;
}
struct node
{
int x_,y_;
};
int main()
{
n=read();m=read();q=read();
cnt=n*m;
for (int i=1;i<=n;i++)
{
cin>>s;
for (int j=0;j<s.size();j++)
{
c[i][j+1]=s[j];
}
for (int j=1;j<=m;j++)
{
if (c[i][j]=='A'||c[i][j]=='.'||c[i][j]=='B')
{
if (c[i-1][j]=='A'||c[i-1][j]=='.'||c[i-1][j]=='B')
{
G[tra(i,j)].push_back(tra(i-1,j));
G[tra(i-1,j)].push_back(tra(i,j));
}
if (c[i][j-1]=='A'||c[i][j-1]=='.'||c[i][j-1]=='B')
{
G[tra(i,j)].push_back(tra(i,j-1));
G[tra(i,j-1)].push_back(tra(i,j));
}
}
if (c[i][j]=='A') begin_a=i,begin_b=j;
if (c[i][j]=='B') end_a=i,end_b=j;
}
}
// cout<<"ff"<<endl;
CST(tra(begin_a,begin_b));
dfs(tra(begin_a,begin_b),0);
BFS(begin_a,begin_b);
queue<node> Q;
if (dis[end_a][end_b-1]) p[end_a][end_b][0]=1,Q.push(node{tra(end_a,end_b),0});
if (dis[end_a][end_b+1]) p[end_a][end_b][1]=1,Q.push(node{tra(end_a,end_b),1});
if (dis[end_a-1][end_b]) p[end_a][end_b][2]=1,Q.push(node{tra(end_a,end_b),2});
if (dis[end_a+1][end_b]) p[end_a][end_b][3]=1,Q.push(node{tra(end_a,end_b),3});
while (!Q.empty())
{
int u=bk1(Q.front().x_),v=bk2(Q.front().x_);
int w=Q.front().y_;
Q.pop();
int x=u-dx[w],y=v-dy[w];
if (x>=1&&x<=n&&y>=1&&y<=m&&c[x][y]!='#'&&p[x][y][w]==0)
{
p[x][y][w]=1;
Q.push(node{tra(x,y),w});
}
for (int i=0;i<4;i++)
{
if (p[u][v][i]==0&&i!=w&&check(tra(u+dx[w],v+dy[w]),tra(u+dx[i],v+dy[i]),tra(u,v))==1&&c[u+dx[i]][v+dy[i]]!='#'&&u+dx[i]>=1&&u+dx[i]<=n&&v+dy[i]>=1&&v+dy[i]<=m)
{
p[u][v][i]=1;
Q.push(node{tra(u,v),i});
}
}
}
while (q--)
{
int a1,a2;
a1=read();
a2=read();
if (c[a1][a2]=='B'||p[a1][a2][0]||p[a1][a2][1]||p[a1][a2][2]||p[a1][a2][3])
{
puts("YES");
}
else puts("NO");
}
return 0;
}