首页 > 代码库 > 地下迷宫(bfs输出路径)
地下迷宫(bfs输出路径)
题解:开一个pre数组用编号代替当前位置,编号用结构题另存,其实也可以i*m+j来代替,我写的有点麻烦了;
代码:
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <queue>using namespace std;#pragma(1)typedef struct Node{ int x, y; int t; int sz; friend bool operator < (Node a, Node b){ return a.t > b.t; }}Node;Node node[10010];priority_queue<Node>Q;int vis[11][11];int mp[11][11];int pre[10010];int disx[4] = {0,0,1,-1};int disy[4] = {1,-1,0,0};int mv(int x, int y){ if(x == 0){ if(y == 1){ return 0; } else if(y == -1){ return 3; } }else if(x == 1){ if(y == 0) return 1; }else if(x == -1){ if(y == 0) return 1; }}void print(int sz){ if(sz == 0)return; print(pre[sz]); printf(",[%d,%d]", node[sz].x, node[sz].y);}void bfs(int n, int m, int p){ Node a,b; a.x = 0, a.y = 0, a.t = p, a.sz = 0; while(!Q.empty()){ Q.pop(); } Q.push(a); memset(vis, 0, sizeof(vis)); memset(pre, 0, sizeof(pre)); memset(node, 0, sizeof(node)); vis[0][0] = 1; node[0] = {0, 0, 0, 0}; int sz = 0; while(!Q.empty()){ a = Q.top(); Q.pop(); for(int i = 0; i < 4; i ++){ b.x = a.x + disx[i]; b.y = a.y + disy[i]; b.t = a.t - mv(disx[i], disy[i]); b.sz = ++sz; node[sz] = {b.x, b.y, b.t, b.sz}; pre[sz] = a.sz; if(b.x < 0 || b.y < 0 || b.x >= n || b.y >= m)continue; if(vis[b.x][b.y])continue; if(b.t < 0)continue; if(mp[b.x][b.y] == 0)continue; if(b.x == 0 && b.y == m - 1){ printf("[%d,%d]",0,0); print(sz); puts(""); return; } vis[b.x][b.y] = 1; Q.push(b); } } puts("Can not escape!"); return;}int main(){ int n, m, q; while(~scanf("%d%d%d", &n, &m, &q)){ memset(mp, 0, sizeof(mp)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%d", &mp[i][j]); } } bfs(n, m, q); } return 0;}
地下迷宫(bfs输出路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。