自动搬运

查看原文

来自洛谷，原作者为

	昨日之日 老年退役选手

搬运于2025-08-24 21:59:02，当前版本为作者最后更新于2019-10-31 16:29:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题如果不考虑洪水的话，就是一道裸的bfs。

加了这个洪水之后只需要处理洪水到达每一个格子的最早时间，在广搜过程中如果遇到有现在的时间大于等于这个格子的洪水到达时间就直接扔掉。

需要注意的是在处理洪水的时候如果当前是避难所或者障碍物就不能加入队列。

另外一个坑点就是会有多个出洪水的点，所以洪水要先赋值成一个很大的值，再用min更新而不是直接赋值。

当时考试的时候没想仔细，其实这里也可以把所有出水点都加入队列，然后再搜索，这样时间复杂度会小很多。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[55][55];
int fx[4][2]={1,0,0,1,-1,0,0,-1};
struct node {
	int x;
	int y;
	int cnt;//当前的时间
};
int water[55][55];
bool h_used[55][55];
queue <node> Water;
node startt,endd;
queue <node> Q;
node X[2505];
int xid;
void Water_Bfs(){
	while(!Water.empty()){
		node noww=Water.front();
		Water.pop();
		noww.cnt++;
		for(int i=0;i<4;i++){
			node _next=noww;
			_next.x+=fx[i][0],_next.y+=fx[i][1];
			if(_next.x<1||_next.y<1||_next.x>n||_next.y>m)continue;
			if(h_used[_next.x][_next.y])continue;
			water[_next.x][_next.y]=min(water[_next.x][_next.y],_next.cnt);
			Water.push(_next);
			h_used[_next.x][_next.y]=1;
		}
	}
}
void Ans_Bfs(){
	Q.push(startt);
	while(!Q.empty()){
		node noww=Q.front();
		Q.pop();
		if(water[noww.x][noww.y]<=noww.cnt)
			continue;
		if(noww.x==endd.x&&noww.y==endd.y){
			cout<<noww.cnt;
			return;
		}
		noww.cnt++;
		for(int i=0;i<4;i++){
			node _next=noww;
			_next.x+=fx[i][0],_next.y+=fx[i][1];
			if(_next.x<1||_next.y<1||_next.x>n||_next.y>m)continue;
			if(h_used[_next.x][_next.y])continue;
			if(a[_next.x][_next.y]=='X')continue;
			Q.push(_next);
			h_used[_next.x][_next.y]=1;
		}
	}
	cout<<"KAKTUS";
}
int main(){
	memset(water,127,sizeof(water));
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			if(a[i][j]=='S'){
				startt.x=i;
				startt.y=j;
				startt.cnt=0;
			}
			if(a[i][j]=='D'){
				endd.x=i;
				endd.y=j;
			}
			if(a[i][j]=='X'){
				X[xid].x=i;
				X[xid++].y=j;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*'){
				node w;
				w.x=i;
				w.y=j;
				w.cnt=0;
				Water.push(w);
				water[i][j]=0;
				memset(h_used,0,sizeof(h_used));
				h_used[endd.x][endd.y]=1;
				for(int k=0;k<xid;k++){
					h_used[X[k].x][X[k].y]=1;
				}
				Water_Bfs();
			}
		}
	}
	water[endd.x][endd.y]=1e8;
	memset(h_used,0,sizeof(h_used));
	h_used[startt.x][startt.y]=1;
	Ans_Bfs();
}