自动搬运

查看原文

来自洛谷，原作者为

	chen_kun 生命绚烂，别被黑暗压垮。

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

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

以下是正文

一道裸的 BFS 模版

但我还是改了很久

首先题意很好理解，给出一个矩阵，让你从左上角走到右下角，问最少多少时间。

看到最短时间就应该马上想到 BFS 吧。

这个小蓝在正常走路的时候只能花费 1 秒向下或向右走，但是它还可以向左或向右往低海拔花费 1 秒滑铲。看到这里当时我想起了滑雪。

显然这道题和滑雪没有什么关系。

那到这里就很明显了，在偏移坐标的时候分类讨论就好了。

这里最原始的代码就不放了。

因为思路奇葩以至于我现在自己都看不懂。

看看我的正解（注释应该能解释我没讲的东西）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,vis[1145][1145],a[1145][1145],dx[5]={1,0,0},dy[5]={0,1};//坐标偏移数组（虽然没什么必要） 
struct node{int x,y,cnt;};//横纵坐标与时间 
void bfs(){
	queue<node>q;
	q.push({1,1,0});
	vis[1][1]=1;
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,cnt=q.front().cnt;//取出队头元素 
		if(x==n&&y==n){cout<<cnt;return;}
		for(int i=0;i<2;i++){//正常走路 
			int tx=x+dx[i],ty=y+dy[i];
			if(vis[tx][ty]==0&&tx>0&&ty>0&&tx<=n&&ty<=n) vis[tx][ty]=1,q.push({tx,ty,cnt+1});
		}
		//滑铲 
		for(int i=y+1;i<=n;i++){//向右滑铲 
			if(a[x][i]<a[x][i-1]){//判断还能不能滑铲 
				if(vis[x][i]==0) q.push({x,i,cnt+1});//判断走没走过并记录滑铲能到的点所需时间 
			}
			else break;//如果滑不动了就退出 
		}
		for(int i=y-1;i>=1;i--){//向左滑铲 
			if(a[x][i]<a[x][i+1]){//同上 
				if(vis[x][i]==0) q.push({x,i,cnt+1});
			}
			else break;
		}
		q.pop();//出队 
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
	bfs();
	return 0;
}
/*

*/

敲黑板！

for(int i=y+1;i<=n;i++){
  if(a[x][i]<a[x][i-1]&&){
    if(vis[x][i]==0) q.push({x,i,cnt+1});
  }
  else break;
}
for(int i=y-1;i>=1;i--){
  if(a[x][i]<a[x][i+1]){
    if(vis[x][i]==0) q.push({x,i,cnt+1});
    }
  else break;
}

这里的话要注意滑铲时判断的两个 if 一定一定要分开，因为跳出循环是因海拔过高不能滑铲而跳出，如果写为

if(a[x][i]<a[x][i-1]&&vis[x][i]==0) q.push({x,i,cnt+1});

他跳出循环的原因可能是这个点走过了，就会导致全 WA 。

题解到这里就结束了。

这是本人的第一篇题解，管理员大大给个批准吧。