迷宫问题【数据结构实验报告】

古城微笑少年丶 2022-06-06 02:16 238阅读 0赞

**数据结构实验报告**

**实验名称**：实验二 迷宫问题

学号：\*\*\*

姓名：gnosed

实验日期：2017.10.23

**一、实验目的**

1、了解回溯法在求解迷宫问题中的应用

2、进一步掌握栈的使用

**二、实验具体内容**

**1、实验题目1：**

**（1）题目**

用回溯法求解迷宫问题，可以用一个栈保存探索的序列。并且在该迷宫的行走中，站在一点可以有八个方向选择。

比如如下的迷宫

Enter-> 0 1 1 1 0 0 0 0 0 0

0 0 0 1 0 0 0 1 0 0

0 1 0 1 1 0 0 1 0 0

0 1 0 0 1 0 1 1 0 0

1 1 1 0 1 0 1 0 0 0

0 0 1 0 0 0 1 0 1 1

0 1 1 0 1 0 1 0 0 0

0 0 0 0 1 0 1 1 0 0 --> EXIT

下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！）

Path: ( maze\[0\]\[0\], maze\[1\]\[0\],maze\[1\]\[1\], maze\[1\]\[2\], maze\[2\]\[2\],

maze\[3\]\[2\], maze\[3\]\[3\], maze\[4\]\[3\],maze\[5\]\[3\], maze\[6\]\[3\],

maze\[6\]\[4\], maze\[6\]\[5\], maze\[5\]\[5\],maze\[4\]\[5\], maze\[3\]\[5\],

maze\[2\]\[5\], maze\[2\]\[6\], maze\[1\]\[6\],maze\[0\]\[6\], maze\[0\]\[7\],

maze\[0\]\[8\], maze\[1\]\[8\], maze\[2\]\[8\],maze\[3\]\[8\], maze\[4\]\[8\],

maze\[5\]\[8\], maze\[5\]\[7\], maze\[6\]\[7\],maze\[7\]\[7\], maze\[8\]\[7\],

maze\[8\]\[8\], maze\[8\]\[9\], maze\[9\]\[9\])

Enter-> X 1 1 1 0 0 X---X---X 0

X---X---X 1 0 0 X 1 X 0

0 1 X 1 1 X---X 1 X 0

0 1 X---X 1 X 1 1 X 0

0 1 0 X 1 X 1 1 X 0

1 1 1 X 1 X 1 X---X 0

0 0 1 X---X---X 1 X 1 1

0 0 1 0 0 0 1 X 1 1

0 1 1 0 1 0 1 X-- X-- X

0 0 0 0 1 0 1 1 0 X --> EXIT

**（2）分析**

规定：

1） 迷宫左上角第一个位置为入口，右下角第一个位置为出口。

2） 探索的方向为从上按顺时针旋转，上下左右四个方向。

3） 输入：m，n和m\*n个迷宫状态，0表示通路，1表示有墙。

4） 输出：若找到走通迷宫的路径，输出路径的各步的位置。否则，提示找不到。

数据结构：

1） 用二维数组MAZE\[m\]\[n\] 来表示迷宫的状态，0表示通路，1表示有墙，2表示已经走过。

2） 用STL的栈储存走过的路径，压栈表示进入下一步，退栈表示返回上一步。每个栈元素是由当前位置坐标。

算法过程：

从入口位置开始，将其入栈。

1）取栈顶元素值（不出栈），

2）按规定方向判断下一步的位置，即除了原走来的方向，判断其余三个方向是否有通路，

3）若发现一个（若第一个位置已走过，则判断下一个）通路的位置，将其入栈；

4）若三个方向都是墙，则出栈。

5）若发现出口，输出路线。若栈空，提示没有路线。若未发现出口而且栈不为空，则重复1）2）3）4）。

**（3）实验代码**

源代码：

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    const int maxm=100,maxn=100;
    int MAZE[maxm][maxn],m,n;
    struct pos{
        int i,j;
    };
    void create(){
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            int t;cin>>t;
            MAZE[i][j]=t;
        }
    }
    struct pos Move(struct pos curr){
        /*判断是否有通路，有则返回通路位置，无则返回原来位置
        重复问题：
        若何判断原来方向
        若何记录哪个位置是第几次走*/
        struct pos next=curr;
        int x=curr.i,y=curr.j;
        //向上
        if(!MAZE[x-1][y]&&(x-1)>=0&&
           MAZE[x-1][y]!=2){
               next.i=x-1;//只有x坐标改变
               MAZE[x-1][y]=2;//标记将要行走
            return next;//返回要下一步的位置
        }//向右
        else if(!MAZE[x][y+1]&&(y+1)<n&&
                MAZE[x][y+1]!=2){
                    next.j=y+1;
                    MAZE[x][y+1]=2;
            return next;
        }//向下
        else if(!MAZE[x+1][y]&&(x+1)<m&&
                MAZE[x+1][y]!=2){
                    next.i=x+1;
                    MAZE[x+1][y]=2;
            return next;
        }//向左
        else if(!MAZE[x][y-1]&&y-1>=0&&
                MAZE[x][y-1]!=2){
                    next.j=y-1;
                    MAZE[x][y-1]=2;
            return next;
        }
        return curr;//无路，返回原来的位置
    }
    void findPath(){
        stack<struct pos> Path;
        struct pos curr,nex;
        curr.i=0;curr.j=0;
        Path.push(curr);//入口入栈
        MAZE[0][0]=2;//标记已走过
        while(!Path.empty()){//5)
            curr=Path.top();//1)
    //        cout<<curr.i<<" "<<curr.j<<endl;
            nex=Move(curr);//2)特别注意重复的问题和边界处理问题
            if(!(curr.i==nex.i&&curr.j==nex.j))//3)发现通路
                Path.push(nex);
            else
                Path.pop();//4)未发现通路
            if(nex.i==m-1&&nex.j==n-1){//5)
                struct pos route[Path.size()];
                int z=0;
                while(!Path.empty()){
                    curr=Path.top();
                    route[z++]=curr;
                    Path.pop();
                }
                for(int k=z-1;k>=0;k--){
                    cout<<"("<<route[k].i<<","<<route[k].j<<")";
                    if(k%5==0)    cout<<endl;
                    if(k)  cout<<"->";
                }
                return ;
            }
        }
        cout<<"NO Path!"<<endl;
    }
    int main(){
        cin>>m>>n;
        create();
        findPath();
        return 0;
    }

测试数据：

Input

10  10
    0   1  1   1   0  0   0   0  0   0
    0   0  0   1   0  0   0   1  0   0
    0   1  0   1   1  0   0   1  0   0
    0   1  0   0   1  0   1   1  0   0
    0   1  0   0   1  0   1   1   0   0
    1   1  1   0   1  0   1   0  0   0
    0   0  1   0   0  0   1   0  1   1
    0   0  1   0   0  0   1   0  1   1
    0   1  1   0   1  0   1   0  0   0
    0   0  0   0   1  0   1   1  0   0

Coutput

(0,0)->(1,0)->(1,1)->(1,2)->(2,2)
    ->(3,2)->(3,3)->(4,3)->(5,3)->(6,3)
    ->(6,4)->(6,5)->(5,5)->(4,5)->(3,5)
    ->(2,5)->(1,5)->(0,5)->(0,6)->(0,7)
    ->(0,8)->(0,9)->(1,9)->(2,9)->(3,9)
    ->(4,9)->(5,9)->(5,8)->(5,7)->(6,7)
    ->(7,7)->(8,7)->(8,8)->(8,9)->(9,9)

Input

10  10
    0   1  1   1   0  0   0   0  0   0
    0   0  0   1   0  0   0   1  0   0
    0   1  0   1   1  0   0   1  0   0
    0   1  0   0   1  0   1   1  0   0
    0   1  0   0   1  0   1   1   0   0
    1   1  1   0   1  0   1   0  0   0
    0   0  1   0   1  0   1   0  1   1
    0   0  1   0   1  0   1   0  1   1
    0   1  1   0   1  0   1   0  0   0
    0   0  0   0   1  0   1   1  0   0

Coutput

NO Path!

**三、实验小结**

1.  首先，在实现代码前，能够分析题目，设计算法，攥写文档，算是自己的一大进步。
2.  敢于实现自己的想法，不局限于老师的提供的方法。比如本实验中，我没有添加迷宫的“墙”，只需在探索时注意界限判断，这节省了空间。
3.  不足之处在于，刚开始结合题目考虑栈元素的结构时不够清晰，导致一时无从设计算法。
4.  本实验最大的教训就是，通过原本通过两个指向结构体的指针判断这两个结构体是否相等。其实我想当然的想判断结构体的值相等，可是函数中返回的是指针，即地址，而且由于不能直接判断两个结构体相等，所以并不能通过指针判断两个结构体相等，导致这个bug藏得很深。换个思路，从其定义出发，既然不能直接判断两个结构体相等，那就判断结构体里面的全部元素类型相等。