自动搬运

查看原文

来自洛谷，原作者为

	little_cindy AFOed，有事烧纸，私信每月可能会看一次吧

搬运于2025-08-24 22:32:59，当前版本为作者最后更新于2021-08-02 15:09:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

橙名之后第一篇题解！

思路

题目的信息很明确，也十分简单，跑个 bfs 就行了。

可是，我们需要求出每一个点到最近的树的曼哈顿距离。

根据曼哈顿距离的定义，其实就是一个点到另一个点的最短路。所以，把所有树的位置放入队列，再用 bfs 求出最短路即可。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int mhd[maxn][maxn],n,m;
bool danger[maxn][maxn],vis[maxn][maxn];
struct wolf{
	int x;
	int y;
	int Manhattan_distance;//Vjekoslav 在逃回窝的途中离它最近的树的距离的最小值
	bool operator < (const wolf &tmp) const {//重载一下运算符
		return Manhattan_distance<tmp.Manhattan_distance;
	} 
};
struct node{
	int x,y,h;
}e,s;
int dx[4]={0,0,1,-1};//方向函数
int dy[4]={1,-1,0,0};
queue<node> nq;
void bfs1(){//求曼哈顿距离
	while(!nq.empty()){
		node cur=nq.front();
		nq.pop();
		mhd[cur.x][cur.y]=cur.h;
		for(int i=0;i<4;i++){
			int nx=cur.x+dx[i];
			int ny=cur.y+dy[i];
			if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!danger[nx][ny]){
				danger[nx][ny]=1;
				nq.push({nx,ny,cur.h+1});
			}
		}
	}
	return;
}
int bfs(int x,int y){//求答案
	int ans=1e9;
	priority_queue<wolf> q;
	vis[x][y]=1;
	q.push({x,y,mhd[x][y]});
	while(!q.empty()){
		wolf cur=q.top();
		q.pop();
		if(cur.x==e.x&&cur.y==e.y) {//取最小答案
			ans=min(ans,cur.Manhattan_distance);
		}
		for(int i=0;i<4;i++){
			int nx=cur.x+dx[i];
			int ny=cur.y+dy[i];
			if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!vis[nx][ny]){
				vis[nx][ny]=1;
				q.push({nx,ny,min(cur.Manhattan_distance,mhd[nx][ny])});
			}
		}
	}
	return ans;//返回答案
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		char a;
    		cin>>a;
    		if(a=='+'){//树
    			danger[i][j]=1;
    			nq.push({i,j,0});
			}
			else if(a=='V'){//起点
				s={i,j};
			}
			else if(a=='J'){//终点
				e={i,j};
			}
		}
	}
	bfs1();
	cout<<bfs(s.x,s.y);
	return 0;
}