稳健

用户名：jxfzzzt

访问量：2289

签　名：

等　　级
排　　名	534
经　　验	4445
参赛次数	6
文章发表	2
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛真题-重复的数
浏览：800

你可能喜欢

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

大神的探险之寻找宝藏-题解(C++代码)

　　作者: 稳健　　　　发表时间：2020-03-26 16:56:52 浏览：921　|　评论：0　

原题链接：大神的探险之寻找宝藏

#1417: 大神的探险 之 寻找宝藏-题解(C++描述) 双端BFS广搜

**题目：cqy终于算出了坑爹的密码！！！进入墓穴，发现墓穴是一个n*m的矩阵。由于墓穴极度缺氧，cqy必须用最短的时间找到唯一的宝藏。墓穴里险象环生，除了有各种各样的陷阱，还有野怪出没！！！cqy每前进一步需要1分钟的时间，如果遇到野怪，还要多花费1分钟来打倒野怪。当然cqy不会往陷阱走，那就有去无回了...如果cqy、宝藏、陷阱、野怪的位置全部已知，那么cqy最短要用多长时间找到宝藏？**

**解释：
因为地图中存在野怪和没有野怪的两个区域， 当不存在野怪时，cqy只需要花费1单位时间便可以到达， 而当存在野怪的时候， cqy就要花费2个单位的时间（包括走路和打怪两部分的时间）。 而又有结论：当图中只存在两种权值的路径的时候，我们可以采取双端BFS进行广搜（具体原因可以看看dijkstra算法的详细证明）**

**双端bfs的技巧：
我们可以利用C++STL中的deque进行双向广搜，当搜到没有怪物的点时，更新当前点的最短路径，并插入队列的前端。 当搜到有怪物的点时， 更新当前点的最短路径， 并插入到队列的最后端。
**

可以利用贪心的角度去理解，当我发现一个只要路径为1的路时，我们肯定会先去走路径为1的路， 然后再去路径为2的路。所以当我们搜到没有怪物的点时，一定会先去搜没有怪物的点的附近的点，所以要插入前端。反之也时一样的。

代码：
```
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <deque>

using namespace std;

typedef pair<int, int> PII;//类似于结构体，用来存点方便点

const int N = 60;
int n, m;
PII start, End;
char g[N][N];//地图数组
int dis[N][N];//记录距离初始点位置的数组
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};//偏移量数组

int bfs() {
    memset(dis, 0x3f, sizeof dis);//初始化无穷大
    dis[start.first][start.second] = 0;
    deque<PII> q;
    q.push_back(start);

while (!q.empty()) {
        PII t = q.front();
        q.pop_front();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m)continue;
            if (g[a][b] == 'X') continue;
            if (g[a][b] == 'E') {
                int w = 1;
                if (dis[a][b] > dis[t.first][t.second] + w) {
                    dis[a][b] = dis[t.first][t.second] + w;
                    q.push_front({a, b});//插入前端
                }
            } else if (g[a][b] == 'T') {
                int w = 2;
                if (dis[a][b] > dis[t.first][t.second] + w) {
                    dis[a][b] = dis[t.first][t.second] + w;
                    q.push_back({a, b});//插入后端
                }
            } else if(g[a][b] == 'A') {
                int w = 1;
                if (dis[a][b] > dis[t.first][t.second] + w) {
                    dis[a][b] = dis[t.first][t.second] + w;
                    q.push_front({a, b});//插入前端，毕竟终点没怪
                }
            }
        }
    }
    return dis[End.first][End.second];//返回值
	//如果返回值无穷大，则说明到达不了
}

int main(void) {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; i++) scanf("%s", g[i]);

for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)//输入地图，并找到起始点和终点
                if (g[i][j] == 'C') start = {i, j};
                else if (g[i][j] == 'A') End = {i, j};

int ans = bfs();//进行搜索
		
//        for(int i=0;i<n;i++)
//        {
//            for(int j=0;j<m;j++)
//                printf("%d ",dis[i][j]);打印dis数组，可以debug
//            puts("");
//        }

if (ans == 0x3f3f3f3f) puts("Game Over!");
        else cout << ans << endl;
    }
	
    return 0;
}
```
##第一次写题解，又不完善的地方多多见谅。

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

稳健

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【计算球体积】（C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

陶陶摘苹果（C语言代码）

大神的探险之寻找宝藏-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

矩阵转置（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

兰顿蚂蚁（C++代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-自由落体问题（C语言代码）

最小公倍数（C语言代码）

稳健

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【计算球体积】 （C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

陶陶摘苹果 （C语言代码）

大神的探险 之 寻找宝藏-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

矩阵转置 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

兰顿蚂蚁 （C++代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

最小公倍数 （C语言代码）

【计算球体积】（C语言代码）

陶陶摘苹果（C语言代码）

大神的探险之寻找宝藏-题解(C++代码)

　　评论区

矩阵转置（C语言代码）

兰顿蚂蚁（C++代码）

C语言训练-自由落体问题（C语言代码）

最小公倍数（C语言代码）