迷宫探险（升级）

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

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

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

样例输入

3
.##
.7.
##.
2
.#
#.

样例输出

11
-1

提示

#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;
}

最后

以上就是飘逸铃铛为你收集整理的迷宫探险（升级）迷宫探险（升级）的全部内容，希望文章能够帮你解决迷宫探险（升级）迷宫探险（升级）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。