亲宝软件园·资讯

展开

C++ 迷宫寻路问题

TssiNG-Z 人气:1

迷宫寻路应该是栈结构的一个非常经典的应用了, 最近看数据结构算法应用时看到了这个问题, 想起来在校求学时参加算法竞赛有遇到过相关问题, 感觉十分亲切, 在此求解并分享过程, 如有疏漏, 欢迎指正

问题描述: 非常简洁明了的问题, 即对于一个由1,0构成的矩阵, 找到一条用0连接起来的从(1,1)到(10,10)的路径

思路: 用栈结构存储路径, 每经过一个点, 将点坐标存入栈, 并在矩阵中将此坐标点值置1, 循环直至找到点(10,10), 若中途没找到可以继续前进的点且栈为空, 则说明当前迷宫无解

代码如下:

  1 #include <iostream>
  2 #include <stack>
  3 
  4 //坐标
  5 typedef struct _struct_pos
  6 {
  7   _struct_pos()
  8   {
  9     x = 0;
 10     y = 0;
 11   }
 12 
 13   int x;
 14   int y;
 15 }Pos;
 16 
 17 //地图
 18 int g_maze_arr[12][12] = {{1,1,1,1,1,1,1,1,1,1,1,1},
 19                           {1,0,1,0,0,0,1,1,0,0,0,1},
 20                           {1,0,1,0,1,0,1,0,0,1,0,1},
 21                           {1,0,1,0,1,0,0,0,1,0,0,1},
 22                           {1,0,0,0,1,1,1,1,0,0,1,1},
 23                           {1,0,1,1,0,0,1,1,0,1,0,1},
 24                           {1,0,1,0,0,1,0,1,0,0,0,1},
 25                           {1,0,0,0,1,0,0,1,1,1,1,1},
 26                           {1,0,1,1,0,0,1,0,0,0,1,1},
 27                           {1,0,0,0,0,1,0,0,1,0,1,1},
 28                           {1,1,1,1,0,0,0,1,1,0,0,1},
 29                           {1,1,1,1,1,1,1,1,1,1,1,1}};
 30 
 31 //路径栈
 32 std::stack<Pos> g_stack_path;
 33 
 34 /***************************************************************
 35 *
 36 */
 37 void print_pos(const Pos &pos)
 38 {
 39   std::cout << "[" << pos.x
 40             << "," << pos.y
 41             << "]" << std::endl;
 42 }
 43 
 44 //检查出口
 45 bool find_next(const Pos &curr_pos, Pos &next_pos)
 46 {
 47   //当前坐标
 48   int x = curr_pos.x;
 49   int y = curr_pos.y;
 50 
 51   //生成四个方向的坐标
 52   Pos top, down, left, right;
 53   top.x   = x;
 54   top.y   = y - 1;
 55   down.x  = x;
 56   down.y  = y + 1;
 57   left.x  = x - 1;
 58   left.y  = y;
 59   right.x = x + 1;
 60   right.y = y;
 61 
 62   //判断四个方向有无通路
 63   if (g_maze_arr[top.x][top.y] == 0)
 64   {
 65     next_pos.x = top.x;
 66     next_pos.y = top.y;
 67     std::cout << "find way : ";
 68     print_pos(next_pos);
 69     return true;
 70   }
 71   else if (g_maze_arr[down.x][down.y] == 0)
 72   {
 73     next_pos.x = down.x;
 74     next_pos.y = down.y;
 75     std::cout << "find way : ";
 76     print_pos(next_pos);
 77     return true;
 78   }
 79   else if (g_maze_arr[left.x][left.y] == 0)
 80   {
 81     next_pos.x = left.x;
 82     next_pos.y = left.y;
 83     std::cout << "find way : ";
 84     print_pos(next_pos);
 85     return true;
 86   }
 87   else if (g_maze_arr[right.x][right.y] == 0)
 88   {
 89     next_pos.x = right.x;
 90     next_pos.y = right.y;
 91     std::cout << "find way : ";
 92     print_pos(next_pos);
 93     return true;
 94   }
 95   else
 96   {
 97     std::cout << "no way find in :";
 98     print_pos(curr_pos);
 99     return false;
100   }
101 }
102 
103 //寻找路径
104 bool find_path()
105 {
106   Pos  st_curr_pos, st_next_pos;
107 
108   //起点
109   st_curr_pos.x = 1;
110   st_curr_pos.y = 1;
111   g_maze_arr[1][1] = 1;
112 
113   //不为终点坐标,继续查找路径
114   while ((st_curr_pos.x != 10) || (st_curr_pos.y != 10))
115   {
116     //找到下一路径
117     if (find_next(st_curr_pos, st_next_pos))
118     {
119       //记录下一个位置并置标记为1
120       g_stack_path.push(st_next_pos);
121       st_curr_pos = st_next_pos;
122       g_maze_arr[st_next_pos.x][st_next_pos.y] = 1;
123     }
124     //无路可走
125     else
126     {
127       //路径栈为空,且无路可退,此迷宫无解
128       if (g_stack_path.empty())
129       {
130         return false;
131       }
132       //根据栈内信息,回退一步
133       else
134       {
135         st_curr_pos = g_stack_path.top();
136         g_stack_path.pop();
137       }
138     }
139   }
140 
141   return true;
142 }
143 
144 //输出路径
145 void print_path()
146 {
147   while (!g_stack_path.empty())
148   {
149     Pos st_curr_pos = g_stack_path.top();
150 
151     std::cout << "[" << st_curr_pos.x
152               << "," << st_curr_pos.y
153               << "]" << std::endl;
154 
155     g_stack_path.pop();
156   }
157 }

测试如下:

结果

加载全部内容

相关教程
猜你喜欢
用户评论