自动搬运

查看原文

来自洛谷，原作者为

	ybwowen **

搬运于2025-08-24 22:27:05，当前版本为作者最后更新于2020-12-27 20:00:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

性质1：在机器人不会碰到岩石的前提下，对于每一个点，我们尽量让初始的机器人直接经过这个点，而不是让副本覆盖到这个点。

证明：因为$D\ge1$，副本向外扩展的速度最多和初始的机器人移动的速度一样快。在合法的前提下，如果机器人能扩展到这个点，那么它一定能够经过这个点。

性质2：在使得经过的点最多的情况下，每个点最多只能经过一次。

证明：根据性质1，我们尽量让初始的机器人直接经过一个点。当我们第二次经过某个点时，相较于第一次到达时我们又多花费了一些时间，机器人要么在这段时间里进行复制，使得我们能够直接经过的点变少，要么虽然还没有复制，但是相较于第一次经过时离下一次复制的时间更近了。

上面两个性质是本题能够使用BFS求解的基础。

我们进行第一遍BFS，初始时向队列里加入每一个‘#’点，计算出每个点所能接受的机器人最多复制的次数，即每个点离它最近的‘#’的距离。

随后我们进行第二遍BFS，初始时向队列里加入每一个起点，尽可能的多经过点。

现在我们该统计答案了。我们如何快速计算出每个点？这也是本题最后一个难点。

对于每个目前我们已经经过的节点，我们将三元组$(x,y,t)$加入一个优先队列中，其中$x,y$是这个点的坐标，$t$是这个点最多能向外扩展多少步，优先队列按照$t$从大到小排序。每次我们取出优先队列的队头，然后向优先队列中加入$(x,y-1,t-1)$，$(x,y+1,t-1)$，$(x-1,y,t-1)$和$(x+1,y,t-1)$，并给这些点打上标记。最后我们统计所有被打上标记的点的个数，就是答案了。

为什么这么做是对的呢？考虑每一个点在上述过程中可能被扩展到多个合法的$t$值，显然$t$值最大的是最优的。通过$t$值从大到小排序，我们保证了每次的扩展都是最优的。

前两次BFS的复杂度是$O(n^2)$的，最后一次BFS中，每一个节点最多只会扩展一次。由于我们使用了一个有限队列，所以时间复杂度为$O(n^2 \log n)$。

总的时间复杂度为$O(n^2 \log n)$。

注意在本题中，是先扩展再复制，对于这种细节我们要进行相应的处理，具体见代码。

#include<bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define lson k<<1
#define rson k<<1|1
//#define getchar nc
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll INF64 = 1e18;

inline char nc(){
	static char buf[100005],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	char ch=getchar(); int sum=0; int f=0;
	while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
	while(isdigit(ch)) sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
	return f?-sum:sum;
}
const int maxn=1e3+5;
int n,d;
char a[maxn][maxn];
int nearest[maxn][maxn];
int v[maxn][maxn];
int ans[maxn][maxn];
int mark[maxn][maxn];
int vis[maxn][maxn];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
struct Node{
	int x,y,t;
};
queue<Node>q; 
inline bool in(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=n;
}
inline bool check(int x,int y,int t){
	return t/d<=nearest[x][y]-1;
}
inline void bfs1(){
	queue<pii>q; while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='#') q.push(mp(i,j)),vis[i][j]=1;
	while(!q.empty()){
		int x=q.front().F,y=q.front().S; q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(!in(xx,yy)||a[xx][yy]=='#'||vis[xx][yy]) continue;
			nearest[xx][yy]=nearest[x][y]+1;
			vis[xx][yy]=1; q.push(mp(xx,yy));
		}
	}
}
inline void bfs2(){
	queue<Node>q; while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(a[i][j]=='S')
				q.push((Node){i,j,0}),v[i][j]=0;
		}	
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,t=q.front().t; q.pop();
		if(t/d>=nearest[x][y]){
			mark[x][y]=1; continue;
		} 
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i],tt=t+1;
			if(!in(xx,yy)||v[xx][yy]!=-1||a[xx][yy]=='#') continue;
			if(check(xx,yy,t)) v[xx][yy]=tt,q.push((Node){xx,yy,tt}); 
		}
	}
}
struct Point{
	int x,y,k;
	bool operator <(const Point &tmp)const{
		return tmp.k>k;
	}
};
inline void bfs3(){
	priority_queue<Point>q; while(!q.empty()) q.pop();
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(v[i][j]!=-1) q.push((Point){i,j,v[i][j]}),vis[i][j]=1;
	while(!q.empty()){
		int x=q.top().x,y=q.top().y,k=q.top().k; q.pop();
		if(!k) continue;
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(!in(xx,yy)||vis[xx][yy]||a[xx][yy]=='#') continue;
			vis[xx][yy]=1; q.push((Point){xx,yy,k-1});
		}
	}
}
int main(){
	n=read(); d=read();
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	bfs1();
	memset(v,-1,sizeof(v));	
	bfs2();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(v[i][j]!=-1){
				v[i][j]/=d;
				if(mark[i][j]) v[i][j]--;
			}
	bfs3();
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			res+=vis[i][j];
	printf("%d\n",res);
	return 0;
}