BFS走迷宫求救

题目如下：黑暗领主卡克图斯得到了魔桶，并且用大水淹没了魔法森林，画家和三只小刺猬不得不尽快回到海狸的洞穴来躲避这场洪水。

魔法森林的地图是一个R行C列的矩阵，其中，空地用“.”表示，洪水泛滥区用”*“表示，岩石用”X“表示，海狸的洞穴用”D“表示，而画家和三个小刺猬的位置用”S“标注。

每分钟画家和三只小刺猬可以移动到他们所在位置的临近区域（上下左右），而洪水每分钟也可以淹没周围四个区域，而洪水和我们的逃亡者们都不能够穿过岩石。当然，他们也不能穿过洪水区，洪水也无法淹没海狸的洞穴。

编写一个程序，输入魔法森林的地图，输出逃亡者们逃到海狸的家的最短用时。

注：画家和三只小刺猬没法进入在同一时间会被淹没的地区。

输入第一行包括两个整数：R C，二者都小于等于50.

接下来的R行每行都有C个字符。地图中只会有一个海狸的洞穴和一个出发地。

输出输出他们逃到海里的洞穴所用的最短的时间。如果他们无法安全逃到海狸的洞穴，就输出“KAKTUS“。

样例:
1.输入
3 3
D.*
...
.S.
1.输出：3
2.输入：
3 3
D.*
...
.S.
2.输出：KAKTUS
3.输入：
3 6
D...*.
.X.X..
....S.
3.输出：6
我的代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,ex,ey,ct[55][55],mpp[55][55],ans[55][55],t;
char mp[55][55];
queue<pair<int,int> > q,qu;
int dx[]= {0,1,0,-1};
int dy[]= {1,0,-1,0};
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			char c;
			cin>>c;
			if(c=='S') {
				mp[i][j]='X';
				q.push(make_pair(i,j));
			}
			if(c=='D') {
				ex=i;
				ey=j;
				mp[i][j]=c;
				mpp[i][j]=2;
				ct[i][j]=2e9;
			}
			if(c=='*') {
				qu.push(make_pair(i,j));
				mp[i][j]=c;
			}
		    if(c=='X'){
		    	mp[i][j]=c;
		    	mpp[i][j]=2;
			}
		}
	}
	while(qu.size()) {
		int x=qu.front().first;
		int y=qu.front().second;
		qu.pop();
		for(int i=0; i<4; i++) {
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&mpp[tx][ty]==0) {
				mpp[tx][ty]=1;
				qu.push(make_pair(tx,ty));
				ct[tx][ty]=ct[x][y]+1;
			}
		}
    }
	while(q.size()) {
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		if(x==ex&&y==ey){
			cout<<ans[ex][ey];
			return 0;
		}
		for(int i=0; i<4; i++) {
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&mp[tx][ty]!='X'&&mp[tx][ty]!='*'&&ans[x][y]+1<ct[tx][ty]) {
				mp[tx][ty]='X';
				q.push(make_pair(tx,ty));
				ans[tx][ty]=ans[x][y]+1;
			}
		}
	}
	cout<<"KAKTUS";
	return 0;
}

我的思路是洪水到达每一个地方的步数先统计出来，然后刺猬他们到达一个地方他们的步数与洪水到达这个地方的步数进行比较，如若比其小，则说明此地没有洪水，可以通过。样例都对，就是后台测试值得60分。望大佬救命（给思路或代码时最好可以附个解释）

讨论操作

回复

相关推荐

BFS走迷宫求救