2020 蓝桥杯大学模拟赛(二) - 结果填空:迷宫题解 电玩女神 2022-12-28 14:15 113阅读 0赞 ### 文章目录 ### * 题目描述 * * 输入 * 算法分析 * * 方法一: * * 如何解决并发性问题呢? * 方法二: * * 如何解决并发性问题呢? * 代码(方法一)(未过,后续修正) * 代码(方法二) -------------------- # 题目描述 # 下图给出了⼀个迷宫的平⾯图,其中标记为 1 的为障碍,标记为 0 的为可以通⾏的地⽅。 010000 000100 001001 110000 迷宫的⼊⼝为左上⻆,出⼝为右下⻆,在迷宫中,只能从⼀个位置⾛到这个它的上、下、左、 右四个⽅向之⼀。 对于上⾯的迷宫,从⼊⼝开始,可以按 DRRURRDDDR 的顺序通过迷宫,⼀共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右⾛。 对于下⾯这个迷宫( 30 ⾏ 50 列),我们可以最上⽅⼀⾏的任意⼀个格⼦作为⼊⼝;以最下⽅ ⼀⾏的任意⼀个格⼦作为出⼝。请找出通过迷宫步数最少的路径有多少条。 ## 输入 ## 01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 01000000001010100011010000101000001010101011001011 00011111000000101000010010100010100000101100000000 11001000110101000010101100011010011010101011110111 00011011010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000 # 算法分析 # 这道题是标准的bfs题目,可以将所有第一行的起点全部压入队列中进行一次bfs。 但是要多考虑一个问题。 ![1][] **因此存在两种解决方法** ## 方法一: ## 普通的bfs**记录步数**,**新增两个变量mmin,cnt**,只有当第一次到达最后一层时,修改**mmin为当前步数**。 在**当步数等于mmin**,并且**达到最后一层时,cnt++**。 ### 如何解决并发性问题呢? ### 在此方法中不使用true和false去标记vist数组,**用当前到达这个点时,它是第几层到达的点,来进行标记** **因此vist数组初始化为-1** ## 方法二: ## 在bfs的基础上,在循环时,**不记录步数**,分层次循环,每次将一层处理完之后再去处理下一层。 **即每次将当前步数能够到达的点,全部处理一边,这样就能保证,在不记录步数的情况下,保证后续出现到终点情况时,步数是相同的并且是最小的。** ### 如何解决并发性问题呢? ### 每次修改时,参照当前层的vist数组,修改下一层的vist1。 **最后在vist数组中无冲突,并且也保证了所有情况修改的综合在vist1中** ## 代码(方法一)(未过,后续修正) ## #include <bits/stdc++.h> using namespace std; char s[55][55]; int vist[55][55]; //记录第几层到达的vist数组 int fx[4][2] = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}}; typedef pair<int, int> pii; typedef pair<int ,pii> piii; int main() { for (int i = 0; i < 30; i++) scanf("%s", s[i]); queue<piii> eq; memset(vist, -1, sizeof(vist)); for(int i = 0; i < 50; i++) if(s[0][i] == '0'){ pii temp; temp.first = 0; temp.second = i; eq.emplace(0,temp); vist[0][i] = 0; } int mmin = 2000, cnt = 0; while(!eq.empty()){ piii now = eq.front(); eq.pop(); if(now.first > mmin) break; for(int i = 0; i < 4; i++){ int nextx = now.second.first + fx[i][0]; int nexty = now.second.second + fx[i][1]; if(nextx < 0 || nextx >= 30 || nexty < 0 || nexty >= 50) continue; if(s[nextx][nexty] == '1') continue; //当将要访问的点一定要高层访问过或者根本被没访问的点 if(vist[nextx][nexty] != -1 && vist[nextx][nexty] < now.first + 1) continue; if(nextx == 29){ mmin = now.first + 1; cnt ++; } pii temp; temp.first = nextx; temp.second = nexty; eq.emplace(now.first + 1, temp); vist[nextx][nexty] = now.first + 1; } } cout << cnt << endl; return 0; } ## 代码(方法二) ## #include <bits/stdc++.h> using namespace std; char s[55][55]; bool vist[55][55]; //当前层,用于判断的层 bool vist1[55][55]; //下一层,用于修改的层 int fx[4][2] = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}}; int main() { for (int i = 0; i < 30; i++) scanf("%s", s[i]); queue<pair<int,int>> eq; for (int i = 0; i < 50; i++) if (s[0][i] == '0') { eq.emplace(0, i); vist[0][i] = 1; } while (1) { int ans = 0; memcpy(vist1, vist, sizeof(vist)); //当前层赋值给下一层 int cnt = eq.size(); if (cnt == 0) return 0; //分层bfs while (cnt--) { auto now = eq.front(); eq.pop(); for (int i = 0; i < 4; i++) { auto nextt = now; nextt.first += fx[i][0]; nextt.second += fx[i][1]; if (nextt.first < 0 || nextt.first >= 30 || nextt.second < 0 || nextt.second >= 50) continue; if (s[nextt.first][nextt.second] == '1') continue; if (nextt.first == 29) ans++; //到达出口 if (vist[nextt.first][nextt.second]) continue; //查看当前这层vist数组 //改变下一层的vist数组 //一层修改一次vist数组,最后综合在vist1数组中 vist1[nextt.first][nextt.second] = 1; eq.emplace(nextt); } } //分层bfs //如果在这层就到达了出口就说明是最短的,并且所有的都记录在内了 if (ans) return printf("%d\n", ans), 0; //如果在这层就到达了出口就说明是最短的,并且所有的都记录在内了 memcpy(vist, vist1, sizeof(vist)); //将下一层赋值给当前层 } return 0; } [1]: /images/20221120/914c8603fb544295ac975c5034d590b4.png
相关 蓝桥杯:迷宫 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 下图给出了一个迷宫的平面图,其中标记为 11 的为障碍,标记为 00 的为可以通行的 水深无声/ 2024年03月25日 22:24/ 0 赞/ 61 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:突破障碍题解 文章目录 题目描述 输入描述 输出描述 数据范围 样例输入 样例输出 算法分析 解题 蔚落/ 2022年12月28日 14:15/ 0 赞/ 116 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:养猫题解 文章目录 题目描述 输入格式 输出格式 数据范围 样例输入 样例输出 算法分析 解题 素颜马尾好姑娘i/ 2022年12月28日 14:15/ 0 赞/ 148 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:分披萨题解 文章目录 题目描述 输入格式 输出格式 数据范围 样例输入 样例输出 算法分析 解题 电玩女神/ 2022年12月28日 14:15/ 0 赞/ 139 阅读
相关 蓝桥杯大学模拟赛(二) - 程序设计:植物大战僵尸题解 文章目录 题目描述 输入描述 输出描述 数据范围 输入 输出 算法分析 算法过程 - 日理万妓/ 2022年12月28日 14:15/ 0 赞/ 147 阅读
相关 2020 蓝桥杯大学模拟赛(二) - 结果填空:迷宫题解 文章目录 题目描述 输入 算法分析 方法一: 如何解决并发性问题呢? 方法二: 电玩女神/ 2022年12月28日 14:15/ 0 赞/ 114 阅读
相关 2020蓝桥杯省赛模拟赛 目录 第一题: 第二题: 第三题: 第四题: 第五题: 第六题: 第七题: 第八题: 第九题: 第十题: 电玩女神/ 2022年12月13日 11:27/ 0 赞/ 180 阅读
相关 蓝桥杯模拟赛:猜算式 你一定还记得小学学习过的乘法计算过程,比如: 请你观察如下的乘法算式 ![这里写图片描述][SouthEast] 星号代表某位数字,注意这些星号中, 0~9中的每个数 Myth丶恋晨/ 2022年06月18日 09:48/ 0 赞/ 252 阅读
还没有评论,来说两句吧...