简单迷宫算法（递归与非递归C++实现）

时间：2023-03-08 16:59:19

假定迷宫如下：1代表墙，0代表道路，起点在（1，1），终点（11，9）（PS:下标从0开始计算）。

简单迷宫算法（递归与非递归C++实现）

现在寻求一条路径能从起点到达终点（非最短）。

有两种解法：递归与非递归。

递归算法思路：

　　要用递归，就要寻找一个子问题，该子问题是递归的。很明显，这道题的子问题就是从8个方向（上下左右还有四个斜角）中寻找一个可行方向并向前走一步，该子问题（seekPath函数）的实现代码如下：

　　

 struct offset{
     int x;
     int y;
 };
 offset move[]={{-,},{-,},{,},{,},{,},{,-},{,-},{-,-}};//8个不同行动方向下的x和y偏移量
 ][]={};//将数组所有节点访问位置0（未访问）
 ]={    ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   "
                 };//迷宫数组
 list<offset> s;//存放成功路径 

 int seekPath(int x,int y){//行动一步
     int next_x,next_y;
     &&y==) ;//找到出口
     ;i<;i++){//朝8个方向试探下一步
         next_x=move[i].x+x;
         next_y=move[i].y+y;
         &&a[next_x][next_y]=='){//下一步未走过并且是道路
             mark[next_x][next_y]=;//标记该点已经走过
             if(seekPath(next_x,next_y)){
                 offset a={next_x,next_y};
                 s.push_front(a); //记录正确路径
                 ;
             }
         }
     }
     &&y==){//死迷宫
         cout<<"failed"<<endl;
     }
         ;
 }

　　递归过程中，在每个点上有8个方向，在某个方向上若能满足“该方向点未走过并且是道路 ”的条件，即可执行下一步（下一步的方向从第一个方向重新开始计算），直到找到递归出口。递归出口自然是行走到终点的情况。

　　测试代码如下：

　　

 int main(){//测试代码
     mark[][]=;
     ,))
         s.push_front(offset{,});
     list<offset>::iterator it=s.begin();
     while(it!=s.end()){
         cout<<"("<<it->x<<","<<it->y<<")";
         it++;
     }
     ;
 }

非递归算法思路：

　　我们首先需要一个辅助链表，链表的作用是为了记录正确路径。从起点开始，有8个方向，若能满足“该方向点未走过并且是道路 ”的条件，即可将该点放入表尾并执行下一步（下一步的方向从第一个方向重新开始计算），当8个方向都不能满足条件时，将该点从表尾删除并回退到上一个点。实现代码如下：

　　

 #include <iostream>
 #include <list>
 using namespace std;
 struct offset{
     int x;
     int y;
 };
 struct point{
     int x;
     int y;
 };
 offset move[]={{-,},{-,},{,},{,},{,},{,-},{,-},{-,-}};//8个不同行动方向下的x和y偏移量
 ][]={};//将数组所有节点访问位置0（未访问）
 ]={    ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   ",
                   "
                 };//迷宫数组 

 int main(){//测试代码
     mark[][]=;
     list<point> lists;//存放路径
     point s={,};
     lists.push_back(s);
     while(!lists.empty()){
         s=lists.back();
         ;d<;d++){//朝8个方向试探下一步
             int x=s.x+move[d].x;
             int y=s.y+move[d].y;
             &&y==){//找到出口
                 s.x=x;
                 s.y=y;
                 lists.push_back(s);
                 goto end;
             }
             ){//下一步未走过并且是道路
                 mark[x][y]=;
                 point temp={x,y};
                 lists.push_back(temp);
                 s.x=x;
                 s.y=y;
                 d=;
             }
         }
             lists.pop_back();//删除不可达路径
     }
     cout<<"failed";
     end:list<point>::iterator it=lists.begin();
     while(it!=lists.end()){
         cout<<"("<<it->x<<","<<it->y<<")";
         it++;
     }
     ;
 }

　　　　

相关文章