迷宫最短路问题

题面

image.png

  简单看一遍题就清楚就很清楚是走迷宫+记录最短路径的问题。难点大概就是 1.dfs遍历一遍去找到最短的路径+2.如何记录下路径然后回溯。

  其实学长上课就讲过类似的一个问题。）首先区别于一般的图论最短路，迷宫两点之间的权值都相同（无权的无向图，直接用一个数组就可以表示），而针对记录路径的过程可以在每个点上都加一个元素father，去记录下该点的前置点（第一个点可以设定前置点就是自己。）随后就可以愉快的dfs一遍，维护一个二维的结构体数组。（因为一开始没好好读题还以为不需要找出来路线所以其实我最后定义了两个结构体）

定义的两个结构体

struct point
{
    int xl;//横坐标 
    int yl;//纵坐标 
    bool ok;//是否能走 
    bool vis;//是否访问过 
};
//记录前置节点而定义的结构体 
struct fa
{
    int x;
    int y;
};

输入与bfs的过程

其中father结构体的设定确实不是很舒服，但完成基本功能是没问题的

for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            al[i][j].xl = i;
            al[i][j].yl = j;
            cin >> al[i][j].ok;
            al[i][j].vis = 0;
        }
    }
    queue<point> que;
    //开一个队列 
    que.push(al[0][0]);
    al[0][0].vis = 1;
    father[0][0].x=0;
    father[0][0].y=0;
    //dfs的过程 
    while (!que.empty())
    {
        point a = que.front();
        que.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int now_x = a.xl + dx[i];
            int now_y = a.yl + dy[i];
            //1.确定没走过 2.确定能走 3.确定没越界 
            if ( now_x >= 0 && now_x < 5 && now_y >= 0 && now_y < 5 && (!al[now_x][now_y].ok) && (!al[now_x][now_y].vis) )
            {
                que.push(al[now_x][now_y]);
                father[now_x][now_y].x =a.xl; 
                father[now_x][now_y].y =a.yl; 
                al[now_x][now_y].vis = 1;
            }
        }
    }

最终的回溯

因为只是要求得到最后的路径，所以维护过程中并没有记录下来各个点的最短路径是多少，只是针对father数组进行了主要的维护，所以回溯过程只能找到路径，不过本题够用了

fa pl[100];
    int i = 0;
    fa px = { 4,4 };
    //回溯路径存到一个数组里面，倒叙输出数组 
    while (px.x!=0||px.y!=0)
    {
        pl[i] = father[px.x][px.y];
        px.x=pl[i].x;
        px.y=pl[i].y;
        i++;
    }
    i--;
    for (int j = i; j >= 0; j--)
    {
        cout << "(" << pl[j].x <<", " << pl[j].y <<")"<< endl;
    }
    cout<<"(4,4)"<<endl;

完整的代码

#include<queue>
#include<iostream>
using namespace std;
//记录点的结构体， 
struct point
{
    int xl;//横坐标 
    int yl;//纵坐标 
    bool ok;//是否能走 
    bool vis;//是否访问过 
};
//记录前置节点而定义的结构体 
struct fa
{
    int x;
    int y;
};
fa father[5][5];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main()
{
    point al[10][10];
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            al[i][j].xl = i;
            al[i][j].yl = j;
            cin >> al[i][j].ok;
            al[i][j].vis = 0;
        }
    }
    queue<point> que;
    //开一个队列 
    que.push(al[0][0]);
    al[0][0].vis = 1;
    father[0][0].x=0;
    father[0][0].y=0;
    //dfs的过程 
    while (!que.empty())
    {
        point a = que.front();
        que.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int now_x = a.xl + dx[i];
            int now_y = a.yl + dy[i];
            //1.确定没走过 2.确定能走 3.确定没越界 
            if ( now_x >= 0 && now_x < 5 && now_y >= 0 && now_y < 5 && (!al[now_x][now_y].ok) && (!al[now_x][now_y].vis) )
            {
                que.push(al[now_x][now_y]);
                father[now_x][now_y].x =a.xl; 
                father[now_x][now_y].y =a.yl; 
                al[now_x][now_y].vis = 1;
            }
        }
    }
    fa pl[100];
    int i = 0;
    fa px = { 4,4 };
    //回溯路径存到一个数组里面，倒叙输出数组 
    while (px.x!=0||px.y!=0)
    {
        pl[i] = father[px.x][px.y];
        px.x=pl[i].x;
        px.y=pl[i].y;
        i++;
    }
    i--;
    for (int j = i; j >= 0; j--)
    {
        cout << "(" << pl[j].x <<", " << pl[j].y <<")"<< endl;
    }
    cout<<"(4,4)"<<endl;
    return 0;
}