首页 > 代码库 > 地下迷宫(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输出路径)