本文主要是介绍初学算法----广度优先搜索--关于记录最优路径的问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

迷宫问题

描述：

定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入：

输出：

样例输入：

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出：

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
像这种问题因为要记录最优路径，所以在一个点访问完后，并且拓展出其周围全部的点后，并不能就丢弃，而是应该储存起来；
然后通过下标，回溯寻找出路径，有一种链表的感觉；
如下是AC代码：

 1 #include<bits/stdc++.h>
 2 #include<cstring>
 3 using namespace std;
 4 struct STR{
 5     int y;
 6     int x;
 7     int fathersub;//通过记录拓展出自己的下标和自己的下标，到最后找到了路径能够遍历打印出
 8     int selfsub;
 9 }mapway[50];
10 int maper[6][6];
11 int vis[6][6];
12 int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
13 int main()
14 {
15     memset(vis,0,sizeof (vis));
16     for (int i=0;i<5;i++)
17     {
18         for (int j=0;j<5;j++)
19         {
20             cin>>maper[i][j];
21         }
22     }
23     vis[0][0]=1;
24     int waysub=0,tracesub=1;
25     ++waysub;
26     mapway[waysub].y=0;
27     mapway[waysub].x=0;
28     mapway[waysub].fathersub=-1;
29     mapway[waysub].selfsub=waysub;
30     while (1)
31     {
32         if (mapway[tracesub].y==4 && mapway[tracesub].x==4)
33         {
34             break;
35         }
36         else
37         {
38             for (int i=0;i<4;i++)
39             {
40                 int nexty=mapway[tracesub].y+dy[i];
41                 int nextx=mapway[tracesub].x+dx[i];
42                 if (nexty<0 || nextx<0 || nexty>4 || nextx>4 || maper[nexty][nextx]==1 || vis[nexty][nextx]==1)
43                 {
44                     continue;
45                 }
46                 else
47                 {
48                     ++waysub;
49                     mapway[waysub].y=nexty;
50                     mapway[waysub].x=nextx;
51                     mapway[waysub].fathersub=mapway[tracesub].selfsub;
52                     mapway[waysub].selfsub=waysub;
53                     vis[nexty][nextx]=1; //千万不要忘记这一步，我写的时候总是忘记导致调试时，很费时间；
54                 }
55             }
56         }
57         tracesub++;
58     }
59 //因为是从最初点到最后点的路径，所以要反一下；
60     int gathersub[50]={0};
61     int waynum=0;
62     int resub=mapway[tracesub].fathersub;
63     gathersub[++waynum]=mapway[tracesub].selfsub;
64     while (1)
65     {
66         if (resub==-1)
67         {
68             break;
69         }
70         gathersub[++waynum]=resub;
71         resub=mapway[resub].fathersub;
72     }
73     reverse(gathersub+1,gathersub+waynum+1);
74     for (int i=1;i<=waynum;i++)
75     {
76         cout<<"("<<mapway[gathersub[i]].y<<","<<" "<<mapway[gathersub[i]].x<<")";
77         if (i!=waynum)
78         {
79             cout<<endl;
80         }
81     }
82     return 0;
83 }

会发现如这段代码很费地方，而且写起来很麻烦，可以有如下优化：

mapway[waysub].y=0;
mapway[waysub].x=0;
mapway[waysub].fathersub=-1;
mapway[waysub].selfsub=waysub;

struct STR{
    int y;
    int x;
    int fathersub;
    int selfsub;
    STR (int yy,int xx,int fsub,int ssub):y(yy),x(xx),fathersub(fsub),selfsub(ssub){}
    STR (){}
};

然后每一次就可以这么写：

 mapway[++waysub]=STR(1,1,-1,waysub);

这是c++的内容：解释一下就是

STR (int yy,int xx,int fsub,int ssub):y(yy),x(xx),fathersub(fsub),selfsub(ssub){}
STR (){}
相当于：

STR (int yy,int xx,int fsub,int ssub){
     int y=yy;
     int x=xx;
     int fathersub=fsub;
     int selfsub=ssub;
}

这篇关于初学算法----广度优先搜索--关于记录最优路径的问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！