原题链接：蓝桥杯算法提高VIP-学霸的迷宫
解题思路:
利用结构体构建节点，其包含数据x,y位置，step走过的步数，way走过的方向存储。
我这一套方法优化程度很低，但是相当好理解。
利用BFS逐个进行搜索，这里需要记住的一点是搜索的顺序必须要按照DLRU这样的字典序进行排列，否则的话会产生一些错误数据。
别忘了使用vis做地图标记，否则的话分分钟爆时。
参考代码:
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<bits/stdc++.h>#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)using namespace std;const int maxn=1005;/*int dir[4][2]= {0,1,0,-1,1,0,-1,0};//右，左，下，上，四个方向这样子用方向会错，原因是需要写字典序最小的 */int dir[4][2]={1,0,0,-1,0,1,-1,0};//按照DLRU的字典序进行排列 int vis[maxn][maxn]; //mark mapchar mp[maxn][maxn]; //map arrayint n,m;struct state { int x,y; int step; string way;};state ans; //答案变量bool check(state s){ if(!vis[s.x][s.y]&&s.x<n&&s.x>=0&&s.y<m&&s.y>=0){ return true; } return false;}bool bfs() { queue<state> q; state now,next,st; st.x=0,st.y=0,st.step=0,st.way=""; q.push(st); vis[st.x][st.y]=1; while(!q.empty()) { now=q.front(); if(now.x==n-1&&now.y==m-1) { ans.x=now.x; ans.y=now.y; ans.step=now.step; ans.way=now.way; return true; } for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; next.step=now.step+1; switch(i) { case 0: next.way=now.way+"D"; break; case 1: next.way=now.way+"L"; break; case 2: next.way=now.way+"R"; break; case 3: next.way=now.way+"U"; break; } if(check(next)){ q.push(next); vis[next.x][next.y]=1; } } q.pop(); } return false;}int main() { hh; cin>>n>>m; memset(vis,0,sizeof(vis)); memset(mp,0,sizeof(mp)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>mp[i][j]; if(mp[i][j]=='1') { vis[i][j]=1; } } } if(bfs()){ cout<<ans.step<<endl; cout<<ans.way<<endl; }else{ cout<<'0'<<endl; } return 0;} |
7.2 分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复