数据结构线性结构（二）6迷宫最短路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构线性结构（二）6迷宫最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构线性结构（二）6迷宫最短路径,数据结构,数据结构,c++,算法

数据结构线性结构（二）6迷宫最短路径,数据结构,数据结构,c++,算法文章来源地址https://www.toymoban.com/news/detail-717868.html

#include <iostream>
#include<queue>

using namespace std;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int map_[1010][1010];
int sx,sy,ex,ey;
void BFS(int x,int y);
void outPath();
struct Node{
    int x,y;
    Node(int x=0,int y=0){
        this->x=x;
        this->y=y;
    }
};
Node **path;
queue<Node> q;
int main()
{
    int x,y;
    cin>>x>>y;
    sx=0;
    sy=0;
    ex=x-1;
    ey=y-1;
    path=new Node *[x];

    for(int i=0;i<x;i++)
    {
        path[i]=new Node[y];

        for(int j=0;j<y;j++) {
            cin>>map_[i][j];
            path[i][j]=Node(0,0);
        }
    }


    BFS(sx,sy);
    outPath();
    return 0;
}

void BFS(int x,int y)
{
    //queue<pair<int,int>> q;
    q.push(Node(x,y));
    while(!q.empty()) {
        Node p=q.front();
        q.pop();
        if(p.x==ex&&p.y==ey) {
            return;
        }
        for(int i=0;i<8;i++) {
            int nx=p.x+dir[i][0];
            int ny=p.y+dir[i][1];
            if(nx<0||nx>=ex+1||ny<0||ny>=ey+1||map_[nx][ny]==1) {
                continue;
            }
            path[nx][ny]=p;
            q.push(Node(nx,ny));
            map_[nx][ny]=1;
        }
    }
    cout<<path[ex][ey].x<<endl;
}

void outPath()
{
    int p=ex,q=ey;
    cout<<"("<<ex+1<<","<<ey+1<<")"<<endl;

    //cout<<path[p][q].x<<endl;
    while(path[p][q].x!=sx||path[p][q].y!=sy ) {
        cout<<"("<<path[p][q].x+1<<","<<path[p][q].y+1<<")"<<endl;
        int t=p;
        p=path[p][q].x;
        q=path[t][q].y;
    }
    cout<<"("<<sx+1<<","<<sy+1<<")"<<endl;
}

/*
6 8
0 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0
0 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0
*/

到了这里，关于数据结构线性结构（二）6迷宫最短路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！