走迷宫问题算法竞赛入门经典

思路分析：

本题可以采取BFS的方式进行解题，我们把每一个节点的下一层节点全部遍历完，并让它们不再次遍历（设置标志数组）。bfs的解决方法是利用队列知识，每次读取一个数据，并让该数据出队，然后把该节点的子节点依次入队，直到最后遍历完毕。

下面贴上代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 #define MAXN 105
 6 int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 7 char name[] = {'U', 'D', 'L', 'R'};
 8 int q[MAXN * MAXN]; //队列，保存当前结点编号
 9 int vis[MAXN][MAXN], nMap[MAXN][MAXN];
10 int m, n; //行、列数
11 int dir[MAXN * MAXN];
12 int fa[MAXN][MAXN], dis[MAXN][MAXN], last_dir[MAXN][MAXN];
13 void funcInit();
14 void bfs(int x, int y);
15 void funcInput();
16 void print_path(int x, int y);
17 int main()
18 {
19     funcInput();
20     funcInit();
21     bfs(0, 0);
22     print_path(m - 1, n - 1);
23     return 0;
24 }
25 void funcInit()
26 {
27     for(int i=0;i!=n;i++)
28     for(int j=0;j!=m;j++)
29     {
30         vis[i][j]=0;dis[i][j]=0;
31     }
32 }
33 void bfs(int x,int y)
34 {
35     int front=0,rear=0;
36     vis[x][y]=1;
37     int u=x*m+y;
38     fa[x][y] = u; //起点元素的父亲为它本身
39     q[rear++]=u;//第一个元素入队
40     while(front<rear)
41     {
42         u=q[front++];//第一个元素出队
43           x=u/m,y=u%m;
44         for(int i=0;i<4;i++)//把出队节点上下左右可以访问的元素依次入队
45         {
46             int nx=x+dx[i],ny=y+dy[i];
47             if(nx>=0&&nx<n&&ny<n&&ny>=0&&!vis[nx][ny]&&!nMap[nx][ny])//在数据范围内并且不是障碍且未被访问过
48             {
49                 vis[nx][ny]=1;//标记为被访问
50                 fa[nx][ny]=u;//设置父节点
51                 int v=nx*m+ny;
52                 q[rear++]=v;//自身入队
53                 dis[nx][ny]=dis[x][y]+1;//距离在父节点的基础上加1
54                 last_dir[nx][ny]=i;//记录父节点到子节点的移动方向
55 
56             }
57         }
58     }
59 }
60 void funcInput()
61 {
62     int i, j;
63     cin>>m>>n;
64     for (i = 0; i != m; ++i)
65     {
66         for (j = 0; j != n; ++j)
67         {
68             cin>>nMap[i][j];
69         }
70     }
71 }
72 void print_path(int x,int y)
73 {
74     int c=0;
75     while(1)
76     {
77      int fx=fa[x][y]/m;
78       int fy=fa[x][y]%m;
79       if(fx==x&&fy==y)
80          break;
81          dir[c++]=last_dir[fx][fy];//把移动方向赋值给数组dir，以便输出路径
82     }
83     while(c--)
84    {
85 
86        cout<<name[dir[c]];
87         cout<<'
';
88     }
89     cout<<"最短路径长度为:"<<dis[m-1][n-1]<<endl;
90 }

注意：需要自己看懂BFS大致模板。

走迷宫问题 算法竞赛入门经典

走迷宫问题算法竞赛入门经典