15011418730 LV 7 @ 2025-8-24 22:21:07

自动搬运

来自洛谷，原作者为

	yangrunze 蓝蓝的天空银河里，有只小白船

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

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

以下是正文

做题之前，让我们先大喊两句：

$\bold{\sout\text{ 荆轲，你刺秦王的英勇事迹将会被全天下的OIers怀恨在心}}$

$\bold{\Large\xcancel\text{荆轲将会臭名昭著}}$

好了，发泄完啦，让我们开始认真做题吧！

一看题目，像个搜索

再一看，像个广度优先搜索

既然是BFS，那我们首先要搞出一个（一堆）队列

那问题是队列里咱们存啥呢？？？

首先，按照广搜解决“迷宫问题”的国际惯例，肯定要先把坐标和步数存到里面！

可是，这似乎不大够？

遇到问题不要怕，~~微笑着面对它~~，从题目中找答案！

荆轲还有两种技能：隐身和瞬移。

隐身：balabala……

瞬移：balabala……

现在给出咸阳城的地图，请计算荆轲到达秦王所在点所需的最短时间。此外，在所用时间相同情况下，荆轲希望使用的两种技能总次数尽可能少；在所用时间与技能次数相同情况下，荆轲希望使用的隐身次数尽可能少。

emmmmm，还要把隐身和瞬移的使用次数存下来~

啊，要存这么多东西……这时候，结构体就要派上用场啦！

~~（结构体是哪位？不是哪位，是用这玩意写高精特别方便的那个结·构·体！）~~

struct qwq{
	int x,y,yx,sy,s;
	//x,y——对应的坐标
	//s——走到这一步的步数
	//yx——隐形使用次数
	//sy——瞬移使用次数
	//（都是用拼音写的呢）
};
queue <qwq> q;//STL超级方便！就是常数大那么亿点

当然，我们要在茫茫多的方案中选择一个最优解——所以，我们要写一个函数（算是取min吧……），来选择一个最优解

qwq minq(qwq a,qwq b){
	if(a.s!=b.s)return a.s<b.s?a:b;//优先选择步数更小的
	if(a.yx+a.sy!=b.yx+b.sy)return a.yx+a.sy<b.yx+b.sy?a:b;//如果步数相等，选择一个技能使用更少的
	return a.yx<b.yx?a:b;//都相等？！那就选一个隐身用的更少的吧
}
qwq ans=(qwq){0,0,233333333,233333333,233333333};//顺便把初始化的ans放出来，当然要挑个大的

所有结构体啥的准备工作都已经完成啦！接下来，咱们考虑一下main函数的框架：包括输入等细节的处理

especially，咱们来康康要输入要注意啥：

输入的整个地图，既有诸如 S T . 之类的字符，还有表示卫兵监控范围的数，两个这么一整合——就用string来输入吧！
由于S啊，T啊啥的随便换个数就行了，只要能标记上就OK，而地图上的数字是非常重要的，所以地图我们用int类型存储
这应该也是每个字符串模拟题要注意的地方，当输入到字符串里的数字 $\ge10$ 的时候，我们要一位一位加上去，（写的时候可以照快读那样写），千万不要读完一位剩下的就不管了
对于每种字符的特殊处理——标记起点和终点，遇到卫兵时，我们要处理出卫兵的观察范围

呼呼，大概就这么多啦~

int n,m,c1,c2,d;//题目描述里的一堆东西
int map[355][355];//地图
int main(){
    ios::sync_with_stdio(false);//关闭流同步，让cin变得快快哒！
	cin>>n>>m>>c1>>c2>>d;//据说cin和scanf混用会出锅？统一用cin
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			string s;
			cin>>s;
			if(s[0]=='S'){//起点
				sx=i,sy=j;//找到起点坐标
				map[i][j]=-1;//标个记
				q.push((qwq){sx,sy,0,0,0});//放到队列里~！
				vis[i][j][0][0]=1;//起点的vis先变成1（vis为啥要开四维？待会再说！（可能大家都已经想到了））
			}
			else if(s[0]=='T'){//终点~
				ex=i,ey=j;//找坐标
				map[i][j]=-2;//标个记
			}
			else if(s[0]=='.')map[i][j]=0;//平凡的空地就不用处理啦
			else{//S，T和.都不是，那就是卫兵啦
				int x=0;//数字读进来
				for(int i=0;i<s.size();i++)
				x=(x<<1)+(x<<3)+(s[i]^'0');//类比快读的原理
				map[i][j]=x;//存到地图里
				lookaround(i,j,x-1);//处理出这只士兵的观察范围，待会讲（重点！）
			}
		}
	}
	bfs();//baidu_first_search（伦敦大雾）
	if(ans.s==233333333)printf("-1");//如果ans没变，那就走不通了
	else printf("%d %d %d",ans.s,ans.yx,ans.sy);//否则输出
	return 0;//功德圆满
}

那接下来的问题来啦！如何处理每个士兵的监控范围呢？

$\large{\text{（前排提示：敲黑板，划重点！！！）}}$

暴力找周围曼哈顿距离 $<a$ 的点？

时间复杂度 $O(a^2)$ ，加上输入的循环 $O(a^2mn)$ ，TLE警告……

那咋办呢？别急，正所谓“举例是理解的试金石”~~（话说我这是第几次用这句话了……反正好久没用了）~~，咱们先画个图！

下图就是 $a=3$ 的情况，士兵可以观察到和它的曼哈顿距离 $\le2$ 的点

（图中， $\bold{\text{黑色}}$ 点为士兵所在点， $\bold{\color{purple}\text{紫色}}$ 点为士兵的监控范围点）

我们惊奇地发现，覆盖区域是一个实心的菱形！

也就是说，士兵观察到的范围，对每一行/列来说，都是一段连续的区间！处理范围，是一个区间修改问题！

提到区间修改，大家会想到什么呢？

线段树？……树状数组？……差分！

众所周知，差分在区间修改问题中有奇效，原因是它只需要改——两个点（不知道为啥？翻我之前题解去，you can also 翻我小伙伴的题解），我们只需要在左端点的位置 $+1$ ，右端点 $+1$ 的位置 $-1$

而且，既然区域是个菱形，我们可别忘了菱形的对称性，也就是说，我们找到一个点之后，我们可以根据它的两条对称轴找到它的三个对应点

也就是说，我们能在 $O(a)$ 的时间内求出一个士兵的监控范围，处理这一块的总复杂度为 $O(amn)$ ，不错不错~

我这里采用的是从中心向四周扩展的方式——也就是说枚举当前点到中心的距离进行修改

（图中， $\bold{\color{green}\text{绿色}}$ 点为修改的左端点， $\bold{\color{orange}\text{橙色}}$ 点为修改的右端点，为了符合我们OIer的坐标书写习惯， $x$ 轴正方向为下方， $y$ 轴正方向为右方）

结合着这个图，你就可以理解下方的代码惹~

在写代码之前，我再bb两句：

差分修改时右端点别忘了加1！！！！！
注意边界的问题，如果超范围了，那就把修改加到边界上（比如右端点为 $n+3$ ，超范围了，那就把这一块的修改改成 $n$ ，左端点同理）

bool look[355][355];//look为能不能看到
int tag[355][355];//tag就是差分数组
void lookaround(int x,int y,int k){//x,y为士兵的坐标，k就是士兵的a值
	for(int i=0;i<=k;i++){//从里向外扩展（由于我们调用的时候已经把k减1了，所以我们这里就是<=k，这样很好写）
		//利用刚才找到的规律进行修改吧！
		//如果理解不了，自己再画图找规律
		tag[max(x-i,1)][max(y-(k-i),1)]++; 
		tag[max(x-i,1)][min(y+(k-i),m)+1]--;
		tag[min(x+i,n)][max(y-(k-i),1)]++;
		tag[min(x+i,n)][min(y+(k-i),m)+1]--;
		//最后别忘了：注 意 细 节
	}
}

那我们如何用tag数组判断一个点是否在士兵的监视范围之内呢？

别忘了：差分的前缀和就是它本身！（自己根据差分和前缀和的定义推一下？）

也就是说，我们对tag数组求一遍前缀和，只要这个和 $>0$ ，就能被看到啦！

我们只需要在main函数里加上这几句：

	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=1;j<=m;j++){
			sum+=tag[i][j];	//就是一个前缀和
			if(sum>0)look[i][j]=1;	
		}
	}

接下来，就是我们的重头戏——广搜的过程啦！

其实只要注意一些细节啥的，广搜根本就不难写

（本题解沿用了vectorwyx同学提供的思路，让我们一起感谢他！）

起初，神创造bfs。

队列是空虚混沌，渊面黑暗；神的灵运行在队首上。

while(!q.empty()){
		qwq fro=q.front();
		q.pop();
   		if(fro.s>ans.s)continue;//最优性剪枝！一定要加上不然会T
		if(fro.x==ex&&fro.y==ey){//找到重点
			ans=minq(ans,fro);//更新最优解
			continue;//之后就没必要搜啦
		}      
		//do something……
}

神说：“要有方向数组”，就有了方向数组。

const int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};//八连通的方向数组
//为了方便瞬移操作，前四个是上下左右，后四个是斜线

神看瞬移是好的，就把方向数组的前后分开了。有晚上，有早晨，是第一日。

		for(int i=0;i<8;i++){//不瞬移，按照八连通方向
        int nx=fro.x+dx[i];//沿着方向数组走
			int ny=fro.y+dy[i];
			//do something...
		}
		if(fro.sy+1>c2)continue;//在瞬移之前，先看看能不能再使用瞬移
		for(int i=0;i<4;i++){//瞬移只能走上下左右
     	  int nx=fro.x+dx[i]*d;//一次可以走d格
			 int ny=fro.y+dy[i]*d;   
			//do something...
		}

神说，士兵的监控范围内要隐身，神就造出判断条件，将隐身的处理，不隐身的处理分开了。事就这样成了。

	if(look[nx][ny]){//如果要走的地方在士兵的监控范围内，需要隐身
   	if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;//如果这个状态到过了，或者超过了隐身使用次数，continue
   	vis[nx][ny][fro.yx+1][fro.sy]=1;//vis变为1
   	q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});//push进去的时候别忘了把隐身次数+1
   }
   else{//不需要隐身就不用判断隐身的使用次数，隐身数也不用+1
   	if(vis[nx][ny][fro.yx][fro.sy])continue;
   	vis[nx][ny][fro.yx][fro.sy]=1;
   	q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});				
   }
  //瞬移的也如法炮制，只要记得把瞬移数+1就OK

神又加了防止越界的措施，有晚上，有早晨，是第二日。

	if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;//如果越界了/这个位置是士兵，不能走

$\cdots\cdots$

不行了不行了我编不下去惹……咱们直接来看完整代码吧！

void bfs(){
	while(!q.empty()){
		qwq fro=q.front();//取队首
		q.pop();//pop
		if(fro.s>ans.s)continue;//最优性剪枝
		if(fro.x==ex&&fro.y==ey){//判断终点
			ans=minq(ans,fro);//更新答案
			continue;
		} 
		for(int i=0;i<8;i++){
			int nx=fro.x+dx[i];
			int ny=fro.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
			if(look[nx][ny]){//不瞬移+隐身
				if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;
				vis[nx][ny][fro.yx+1][fro.sy]=1;
				q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});
			}
			else{//不瞬移+不隐身
				if(vis[nx][ny][fro.yx][fro.sy])continue;
				vis[nx][ny][fro.yx][fro.sy]=1;
				q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});				
			}
		}
		if(fro.sy+1>c2)continue;
		for(int i=0;i<4;i++){
			int nx=fro.x+dx[i]*d;
			int ny=fro.y+dy[i]*d;
			if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
			if(look[nx][ny]){//瞬移+隐身
				if(vis[nx][ny][fro.yx+1][fro.sy+1]||fro.yx+1>c1)continue;
				vis[nx][ny][fro.yx+1][fro.sy+1]=1;
				q.push((qwq){nx,ny,fro.yx+1,fro.sy+1,fro.s+1});
			}
			else{//瞬移+不隐身
				if(vis[nx][ny][fro.yx][fro.sy+1])continue;
				vis[nx][ny][fro.yx][fro.sy+1]=1;
				q.push((qwq){nx,ny,fro.yx,fro.sy+1,fro.s+1});				
			}			
		}
	}

所有的地方都讲完啦！我们来看看完整代码吧！

注意：如果你的代码被卡常而TLE了，请用 C艹17 吸氧提交

（据说是因为新版本的编译器用 STL 会更快？）

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct qwq{//qwq结构体
	int x,y,yx,sy,s;
};
qwq minq(qwq a,qwq b){//找最优解
	if(a.s!=b.s)return a.s<b.s?a:b;
	if(a.yx+a.sy!=b.yx+b.sy)return a.yx+a.sy<b.yx+b.sy?a:b;
	return a.yx<b.yx?a:b;
}
bool vis[355][355][20][20],look[355][355];//一堆杂七杂八的东西
int tag[355][355];
int n,m,c1,c2,d;
int map[355][355];
const int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
void lookaround(int x,int y,int k){//处理看到的范围（差分数组tag）
	for(int i=0;i<=k;i++){
		tag[max(x-i,1)][max(y-(k-i),1)]++; 
		tag[max(x-i,1)][min(y+(k-i),m)+1]--;
		tag[min(x+i,n)][max(y-(k-i),1)]++;
		tag[min(x+i,n)][min(y+(k-i),m)+1]--;
	}
}
int sx,sy,ex,ey;
queue <qwq> q;//队列
qwq ans=(qwq){0,0,233333333,233333333,233333333};
void bfs(){//广搜
	while(!q.empty()){
		qwq fro=q.front();
		q.pop();
		if(fro.s>ans.s)continue;
		if(fro.x==ex&&fro.y==ey){
			ans=minq(ans,fro);
			continue;
		} 
		for(int i=0;i<8;i++){
			int nx=fro.x+dx[i];
			int ny=fro.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
			if(look[nx][ny]){
				if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;
				vis[nx][ny][fro.yx+1][fro.sy]=1;
				q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});
			}
			else{
				if(vis[nx][ny][fro.yx][fro.sy])continue;
				vis[nx][ny][fro.yx][fro.sy]=1;
				q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});				
			}
		}
		if(fro.sy+1>c2)continue;
		for(int i=0;i<4;i++){
			int nx=fro.x+dx[i]*d;
			int ny=fro.y+dy[i]*d;
			if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
			if(look[nx][ny]){
				if(vis[nx][ny][fro.yx+1][fro.sy+1]||fro.yx+1>c1)continue;
				vis[nx][ny][fro.yx+1][fro.sy+1]=1;
				q.push((qwq){nx,ny,fro.yx+1,fro.sy+1,fro.s+1});
			}
			else{
				if(vis[nx][ny][fro.yx][fro.sy+1])continue;
				vis[nx][ny][fro.yx][fro.sy+1]=1;
				q.push((qwq){nx,ny,fro.yx,fro.sy+1,fro.s+1});				
			}			
		}
	}
}
int main(){//main函数
    ios::sync_with_stdio(false);
	cin>>n>>m>>c1>>c2>>d;
	for(int i=1;i<=n;i++){//输入+处理
		for(int j=1;j<=m;j++){
			string s;
			cin>>s;
			if(s[0]=='S'){
				sx=i,sy=j;
				map[i][j]=-1;
				q.push((qwq){sx,sy,0,0,0});
				vis[i][j][0][0]=1;
			}
			else if(s[0]=='T'){
				ex=i,ey=j;
				map[i][j]=-2;
			}
			else if(s[0]=='.')map[i][j]=0;
			else{
				int x=0;
				for(int i=0;i<s.size();i++)
				x=(x<<1)+(x<<3)+(s[i]^'0');
				map[i][j]=x;
				lookaround(i,j,x-1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=1;j<=m;j++){
			sum+=tag[i][j];	//求出look数组（前缀和）
			if(sum>0)look[i][j]=1;	
		}
	}	
	bfs();//广搜
	if(ans.s==233333333)printf("-1");
	else printf("%d %d %d",ans.s,ans.yx,ans.sy);//最后输出
	return 0;
}

$\huge{\mathscr{\color{magenta}THE}}$ $\huge{\mathscr{\color{springgreen}END}}$

（顺便祝大家开学快乐鸭www）

ID

5505

时间

3000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[NOI Online #2 入门组] 荆轲刺秦王

信息

1 条题解

自动搬运

以下是正文

[NOI Online #2 入门组] 荆轲刺秦王

信息

还没有账户？

登录