迷宫探险（升级）迷宫探险（升级）

103 阅读 0 评论 68 点赞

我是靠谱客的博主飘逸铃铛，这篇文章主要介绍迷宫探险（升级）迷宫探险（升级），现在分享给大家，希望可以做个参考。

迷宫探险（升级）

题目描述
探险家小曹来到了一个N*N的迷宫，起点是左上角(1,1)，终点是右下角(N,N)。迷宫由通道，障碍物和墙壁组成，每一步可以花费单位时间向邻接的上下左右四格的通道移动，也可以从通道移动到障碍物，清除障碍物需要一定的时间。请求出从起点到终点所需的最少时间。

输入
输入有多组数据，不超过10组。
每组第一行一个整数N（1<=N<=100）。
第2~N+1行表示迷宫，每行有N个字符。字符# .分别代表墙壁、通道。保证起点(1,1)和终点(N,N)都是通道。字符’1’~'9’代表该区域需要逗留相应的时间来清除障碍物。

输出
每组数据输出一行，一个整数代表从起点所需的最少时间。如果从起点不能到达终点，则输出-1。

样例输入

复制代码

1
2
3
4
5
6
7
8
3
.##
.7.
##.
2
.#
#.

样例输出

复制代码

提示

复制代码

#include<iostream>
#include<queue> // priority_queue 优先队列的头文件 
using namespace std;
const int N = 1e2 + 10;
// 定义数据类型 node x，y 为坐标 dis 为该坐标到起点的距离 
struct node{
int x,y,dis;
};
int n;
char g[N][N];
// 地图 
// 重载 < 定义小根堆 priority_queue默认为大根堆 
bool operator < (const node & a, const node & b){
return a.dis > b.dis;
}
void bfs(){
priority_queue<node> q;	// 定义小根堆 每次抛出 到起点距离最近的点 
q.push({1,1,0}); // 将起点插入到队列中 
g[1][1] = '#'; // 将走过的路置为不通 
while(!q.empty()){
node nq = q.top(); // 将队头取出 
q.pop(); // 将队头抛出 
if(nq.x == n && nq.y == n){ // 当找到终点就退出 
cout <<nq.dis<< endl;
return;
}
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1}; // 定义每次移动的偏移量 
for(int i = 0; i < 4;i++){
int x = nq.x + dx[i],y = nq.y + dy[i]; // 计算每次移动后的坐标 
// 判断移动后的点是否在地图内
// 判断移动后的点是否通 
if(x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] != '#'){
node t = {x,y,0};
if(g[x][y] <= '9' && g[x][y] >= '0'){ // 判断该点是否需要清除障碍 
t.dis += g[x][y] - '0';
}
t.dis += nq.dis + 1; // 移动 
q.push(t); // 插入队列 
g[x][y] = '#'; // 走过即置为不通 
}
}
}
cout << -1 <<endl; // 如果没走到终点即无答案 
}
int main(){
while(cin >> n){
for(int i = 1; i <= n;i++)
for(int j = 1; j <= n;j++)
cin >>g[i][j];
bfs();
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<queue> // priority_queue 优先队列的头文件 
using namespace std;
const int N = 1e2 + 10;
// 定义数据类型 node x，y 为坐标 dis 为该坐标到起点的距离 
struct node{
int x,y,dis;
};
int n;
char g[N][N];
// 地图 
// 重载 < 定义小根堆 priority_queue默认为大根堆 
bool operator < (const node & a, const node & b){
return a.dis > b.dis;
}
void bfs(){
priority_queue<node> q;	// 定义小根堆 每次抛出 到起点距离最近的点 
q.push({1,1,0}); // 将起点插入到队列中 
g[1][1] = '#'; // 将走过的路置为不通 
while(!q.empty()){
node nq = q.top(); // 将队头取出 
q.pop(); // 将队头抛出 
if(nq.x == n && nq.y == n){ // 当找到终点就退出 
cout <<nq.dis<< endl;
return;
}
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1}; // 定义每次移动的偏移量 
for(int i = 0; i < 4;i++){
int x = nq.x + dx[i],y = nq.y + dy[i]; // 计算每次移动后的坐标 
// 判断移动后的点是否在地图内
// 判断移动后的点是否通 
if(x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] != '#'){
node t = {x,y,0};
if(g[x][y] <= '9' && g[x][y] >= '0'){ // 判断该点是否需要清除障碍 
t.dis += g[x][y] - '0';
}
t.dis += nq.dis + 1; // 移动 
q.push(t); // 插入队列 
g[x][y] = '#'; // 走过即置为不通 
}
}
}
cout << -1 <<endl; // 如果没走到终点即无答案 
}
int main(){
while(cin >> n){
for(int i = 1; i <= n;i++)
for(int j = 1; j <= n;j++)
cin >>g[i][j];
bfs();
}
return 0;
}