自动搬运

查看原文

来自洛谷，原作者为

	dOvOb 这个家伙是条懒狗，什么也不想留下

搬运于2025-08-24 22:52:32，当前版本为作者最后更新于2024-11-13 20:21:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设由一行中不为岩石墙的方块组成的连通块为“行连通块”。同理，我们可以定义“列连通块”。那么在一个格子上放置炸弹，就会将这个格子所在的行连通块和列连通块中的所有点都变成空地。

我们容易发现，我们不会在走出炸弹所在的行连通块（或列连通块）之后再走回来，因为这样一定劣于直接从行连通块内部走过去。这就使得被炸弹影响到的区域在最后我们走出的路径中一定构成一段连续的子区间。

我们把原问题转换到图上，原先的一个格子就对应到图中的一个点。每个格子对应的点向自己上下左右的格子对应的点连边。如果边的两边有一边是墙，那么边权就为 $+\infty$ ，否则边权为 $1$ 。

先考虑最终的路径只经过炸弹所在的行连通块的情况，那么问题就转化为：有一次机会使路径上的一段点之间的边权变成 $1$ ，求从起点到终点的最短路。

很显然这个问题可以用分层图来解决。我们只需要建三层图，分别表示“走进选定的行连通块前”、“在选定的行连通块内”、“离开选定的行连通块后”。第一层和第三层图正常连边，第二层图中，如果两个格子属于同一个行连通块且相邻，那么它们对应的点之间连一条权为 $1$ 的边。第一层图中的格子和这个格子在第二层图中相邻的格子之间连边，权为 $1$ ，第二层格子和第三层格子类似地连边。在产生的新图中，起点到终点的最短路就是只经过行联通块的答案。

现在考虑列连通块。我们先考虑路径先经过行连通块再经过列连通块的情况，而且选择的列连通块必须与行联通块相交。这时，只需要在上面的图的第二层和第三层之间加入一层代表“列连通块”的层就可以了。原先的第三层这时变成第四层，不再直接和第二层连边。这一层的点之间可以仿照“行联通块”层连边。通过只在第二层和第三层的对应位置之间连权为 $0$ 的边，我们就可以约束选择的列连通块与行连通块相交。第三层和第四层仿照前面连边。

先经过列连通块再经过行连通块的情况是类似的，只需要再增加两层图即可。最后做一次 bfs 即可求出答案和路径。在路径中找到选择的行连通块与列连通块的交点，就是炸弹放置的位置。

时间、空间复杂度均为 $O(const\times n^2)$

值得注意的是，本题的空间限制比较紧，所以我们不需要真的把图建出来。可以只在 bfs 时处理一下。

AC代码：

#include<bits/stdc++.h>
using namespace std;
constexpr int mxn{1005},mxp{mxn*mxn*6};
vector<int>graph[mxp],layertr[10];
int dis[mxp],pre[mxp],n,s,t;
char mp[mxn][mxn];
bool canpass(char ch)
{
	return ch=='P'||ch=='K'||ch=='.';
}
int point(int x,int y,int layer)
{
	return n*n*layer+x*n+y;
}
void bfs(int s)
{
	fill_n(dis,n*n*6,1e9);
	fill_n(pre,n*n*6,-1);
	list<int>Q;
	dis[s]=0;
	Q.push_back(s);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop_front();
		int layer=u/n/n,x=u%(n*n)/n,y=u%(n*n)%n;
		auto push=[u,&Q](int w){
			return [u,&Q,w](int v){
				if(dis[v]==1e9)
				{
					dis[v]=dis[u]+w;
					pre[v]=u;
					if(w)
						Q.push_back(v);
					else
						Q.push_front(v);
				}
			};
		};
		if(layer==5||layer==0)
		{//last layer
			if(canpass(mp[x][y]))
			{
				auto nx=push(1);
				if(x&&canpass(mp[x-1][y]))
					nx(u-n);
				if(x+1<n&&canpass(mp[x+1][y]))
					nx(u+n);
				if(y&&canpass(mp[x][y-1]))
					nx(u-1);
				if(y+1<n&&canpass(mp[x][y+1]))
					nx(u+1);
			}
		}
		if(layer==0&&mp[x][y]!='X')
		{
			auto pb=[u,&push](int i,int j){
				if(0<=i&&i<n)
				{
					if(0<=j&&j<n)
					{
						if(mp[i][j]!='X')
						{
							push(1)(point(i,j,1));
							push(1)(point(i,j,2));
						}
					}
				}
			};
			pb(x,y+1);pb(x,y-1);
			pb(x+1,y);pb(x-1,y);
		}
		for(int vlayer:layertr[layer])
			push(0)(point(x,y,vlayer));
		for(int v:graph[u])
		{
			if(dis[v]==1e9)
			{
				if(v%(n*n)==u%(n*n))
					push(0)(v);
				else
					push(1)(v);
			}
		}
	}
}
void addedge(int u,int v)
{
	graph[u].push_back(v);
}
void addedge2(int u,int v)
{
	// cerr<<u<<' '<<v<<'\n';
	addedge(u,v);
	addedge(v,u);
}
vector<int>getpath(int t)
{
	vector<int>res;
	for(;t!=-1;t=pre[t])
		res.push_back(t);
	reverse(res.begin(),res.end());
	return res;
}
void print(vector<int>const&p)
{
	for(auto it=p.begin(),jt=next(it);jt!=p.end();++it,++jt)
	{
		if(*it<3*n*n&&*jt>=3*n*n&&*it%(n*n)==*jt%(n*n))
		{
			int p=*it%(n*n);
			cout<<p/n+1<<' '<<p%n+1<<'\n';
			return;
		}
	}
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(canpass(mp[i][j]))
			{
				cout<<i+1<<' '<<j+1<<'\n';
				return;
			}
		}
	}
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			cin>>mp[i][j];
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			// if(i&&canpass(mp[i][j])&&canpass(mp[i-1][j]))
			// 	addedge2(point(i,j,0),point(i-1,j,0));
			// if(j&&canpass(mp[i][j])&&canpass(mp[i][j-1]))
			// 	addedge2(point(i,j,0),point(i,j-1,0));
			auto conn=[i,j](int lu,int lv){
				addedge(point(i,j,lu),point(i,j,lv));
			};
			auto conn2=[i,j](int di,int dj){
				int x=i+di,y=j+dj;
				if(0<=x&&x<n)
				{
					if(0<=y&&y<n)
					{
						addedge(point(i,j,3),point(x,y,5));
						addedge(point(i,j,4),point(x,y,5));
					}
				}
			};
			if(mp[i][j]!='X')
			{
				// conn(0,1);conn(0,2);
				// conn(1,4);conn(2,3);
				// conn(3,5);conn(4,5);
				conn2(0,1);conn2(0,-1);
				conn2(1,0);conn2(-1,0);
				if(mp[i][j]=='P')
					s=point(i,j,0);
				if(mp[i][j]=='K')
					t=point(i,j,5);
			}
		}
	}
	layertr[0]={1,2};
	layertr[1]={4};
	layertr[2]={3};
	layertr[3]={5};
	layertr[4]={5};
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(mp[i][j]!='X')
			{
				if(i&&mp[i-1][j]!='X')
				{
					for(int l:{1,3})
						addedge2(point(i,j,l),point(i-1,j,l));
					// addedge(point(i,j,0),point(i-1,j,2));
					// addedge(point(i-1,j,0),point(i,j,2));
				}
				if(j&&mp[i][j-1]!='X')
				{
					for(int l:{2,4})
						addedge2(point(i,j,l),point(i,j-1,l));
					// addedge(point(i,j,0),point(i,j-1,1));
					// addedge(point(i,j-1,0),point(i,j,1));
				}
			}
			
		}
	}
	bfs(s);
	if(dis[t]==1e9)
	{
		cout<<"NIE\n";
	}
	else
	{
		cout<<dis[t]<<'\n';
		auto p=getpath(t);
		print(p);
		int last=s;
		for(int i:p)
		{
			i%=n*n;
			if(i!=last)
			{
				if(i==last+1)
					cout<<'P';
				if(i==last-1)
					cout<<'L';
				if(i==last+n)
					cout<<'D';
				if(i==last-n)
					cout<<'G';
				last=i;
			}
		}
	}
	// for(int i:getpath(t))
	// 	cerr<<i<<' ';
	// for(int u,v;cin>>u>>v;)
	// {
	// 	cerr<<count(graph[u].begin(),graph[u].end(),v)<<'\n';
	// }
	return 0;
}
// 11
// K..........
// XXXXXXXXXX.
// #..........
// .XXXXXXXXXX
// #.........#
// XXXXXXXXXX.
// ...........
// .XXXXXXXXXX
// ...........
// XXXXXXXXXX.
// P..........
// ans:
// 70
// 5 1