【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;

}

巴特西

【BZOJ5138】[Usaco2017 Dec]Push a Box（强连通分量）

【BZOJ5138】[Usaco2017 Dec]Push a Box（强连通分量）

题面

题解

最新文章

热门文章