首页 > 代码库 > 迷宫问题，手动模拟栈

迷宫问题，手动模拟栈

2024-07-06 02:26:29   222人阅读

（1）迷宫问题

①问题描述

这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。

简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。

 

图1 迷宫示意图

迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。

②基本要求

  • 设计迷宫的存储结构。

  • 设计通路的存储结构。

  • 设计求解通路的算法。

  • 设计迷宫显示和通路的显示方式。

  • 输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。

  • 输出：迷宫、入口、出口及通路路径。

③实现提示

  • 存储设计

迷宫：以一个m×n的数组表示迷宫，如图3所示。数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。

1

1

1

1

1

1

1

1

1

0

0

1

0

0

0

1

1

1

0

0

0

0

0

1

1

0

0

1

0

1

0

1

1

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

图2 迷宫存储示意图

方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把东、南、西、北依次编号为0、1、2、3.其增量数组move[4]如图3所示。

move[4]

x

y

1

1

0

2

0

1

3

-1

0

4

0

-1

图3 数组move[4]

通路：通路上的每一个点有3个属性：一个横坐标属性x、一个列坐标属性y和一个方向属性d，表示其下一点的位置。如果约定尝试的顺序为东、南、西、北，则每尝试一个方向不通时，d值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。

  • 算法设计

要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步，重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。

寻找通路的算法思想如下：

Setp1：入口点坐标及到达该点方向（设为-1）入栈。

Step2：当栈不空时循环执行下列操作：

2.1 栈顶元素出栈至（x,y,d）。

2.2 按预设定顺序求出下一个要试探的方向d++，执行下述操作：

2.2.1 如果方向d可走，则：

2.2.1.1 将（x,y,d）入栈。

2.2.1.2 求新点坐标，得新（x,y）。

2.2.1.3 如果新点（x,y）是终点，则试探结束；
否则，置d=0。

2.2.2否则，试探下一个方向，d++。

Setp3：栈空，表示没有通路；否则，出栈，得到通路路径。

④测试与运行

  • 当迷宫数组为图3所示时，（1,1）为入口，（4,6）为出口，则可能的通路为：
    通路1：（1,1）、（1,2）、（2,2）、（3,2）、（4,2）、（4,3）、（4,4）、（4,5）、（4,6）
    通路2：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（3,4）、（4,4）、（4,5）、（4,6）
    通路3：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（2,5）、（2,6）、（3,6）、（4,6）

  • 重设迷宫，使得没有通路，进行测试。

⑤思考

    • 若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北），如何修改程序？

    • 如何求得所有通路？

    • 如何求得最短通路？

 

 

 

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
class Stack
{
public:
    struct Node//栈里有三个变量和一个指针
    {
        int x;
        int y;
        int d;//方向
        Node * next;
        Node():next(NULL) {}
        Node(int a,int b,int c):x(a),y(b),d(c),next(NULL) {}
    };
    int length;
    Node * topOfStack;//栈顶指针
 
    Stack(int a,int b ,int c)//构造函数 赋值
    {
        int length = 1;
        Node * p = new Node(a,b,c);
        topOfStack = p;
    }
    void push(int  a,int  b,int  c)//入栈
    {
        Node * p = new Node(a,b,c);
        p -> next = topOfStack;
        topOfStack = p;
        length ++;
    }
    void pop()//出栈
    {
        Node * p = topOfStack -> next;
        delete topOfStack;
        topOfStack = p;
        length --;
    }
    void print()//打印
    {
        Node * p = topOfStack;
        while(p !=NULL)
        {
            cout<<"("<<p->x<<","<<p->y<<")"<<endl;
            cout<<"↑"<<endl;
            p = p -> next;
        }
    }
    bool isEmpty()//判断是不是空栈
    {
        if(topOfStack == NULL)return true;
        else return false;
    }
    void Clear()//删除栈中元素
    {
 
        while(!isEmpty())
        {
            Node * p = topOfStack;
            topOfStack = topOfStack -> next;
            delete p;
            p = topOfStack;
        }
    }
};
int main()
{
    //freopen("in.cpp","r",stdin);
    cout<<"please input m and n"<<endl;
    int m,n;
    while(cin>>m>>n)
    {
        int Map[m][n];
        int road[m][n];//记录该节点是否被访问，0代表没访问过，1代表访问过
        for(int i = 0 ; i < m ; i++)
        {
            for( int j = 0 ; j < n ; j++)
            {
                cin>>Map[i][j];
            }
        }
        memset(road,0,sizeof(road));//对road清零处理
        cout<<"entrance:"<<endl;
        int entr[1][2];//入口坐标
        cin>>entr[0][0]>>entr[0][1];
        cout<<"exit:"<<endl;
        int exit[1][2];//出口坐标
        cin>>exit[0][0]>>exit[0][1];
        int d[6]= {0,1,2,3,4,5}; //1左 2下 3右 4上
        if((Map[entr[0][0]][entr[0][1]]==1)||(Map[exit[0][0]][exit[0][1]]==1))
        {
            cout<<"input error"<<endl;
            continue;
        }
        Stack dusk(entr[0][0],entr[0][1],d[1]);//把入口坐标和方向1压入栈
        road[entr[0][0]][entr[0][1]]=1;//入口坐标被访问
 
        while((dusk.topOfStack->x != exit[0][0])||(dusk.topOfStack->y != exit[0][1]))
            //当入口坐标和出口坐标的x，y有一个不一样就循环
 
        {
            if(dusk.topOfStack->d == d[1])//方向1
            {
 
                if(Map[dusk.topOfStack->x][dusk.topOfStack->y-1] == 0
                        && dusk.topOfStack->x>=0
                        && dusk.topOfStack->x<=m
                        &&dusk.topOfStack->y-1>=0
                        &&dusk.topOfStack->y-1<=n
                        &&road[dusk.topOfStack->x][dusk.topOfStack->y-1]==0)
                    //满足左边的节点没被访问、值为0、在n*m内，就把左边的节点压入栈
                {
 
 
                    dusk.push(dusk.topOfStack->x,dusk.topOfStack->y-1,d[1]);
                    road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
                }
 
                else
                {
                    //如果不满足，方向+1
                    dusk.topOfStack->d ++;
                }
            }
 
            if(dusk.topOfStack->d == 2)
 
            {
 
                if(Map[dusk.topOfStack->x+1 ][dusk.topOfStack->y] == 0
                        && dusk.topOfStack->x+1>=0 && dusk.topOfStack->x+1<=m
                        &&dusk.topOfStack->y>=0&&dusk.topOfStack->y<=n
                        &&road[dusk.topOfStack->x+1][dusk.topOfStack->y]==0
                  )
                {
 
                    dusk.push(dusk.topOfStack->x+1,dusk.topOfStack->y,d[1]);
                    road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
 
                }
 
                else
                {
 
                    dusk.topOfStack->d ++;
                }
            }
            if(dusk.topOfStack->d == 3)
            {
 
                if(Map[dusk.topOfStack->x][dusk.topOfStack->y+1] == 0
                        && dusk.topOfStack->x>=0 && dusk.topOfStack->x<=m
                        &&dusk.topOfStack->y+1>=0&&dusk.topOfStack->y+1<=n
                        &&road[dusk.topOfStack->x][dusk.topOfStack->y+1]==0)
                {
 
                    dusk.push(dusk.topOfStack->x,dusk.topOfStack->y+1,d[1]);
                    road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
 
                }
 
                else
                {
                    dusk.topOfStack->d ++;
                }
            }
            if(dusk.topOfStack->d == 4)
            {
                if(Map[dusk.topOfStack->x-1][dusk.topOfStack->y] == 0
                        && dusk.topOfStack->x-1>=0 && dusk.topOfStack->x-1<=m
                        &&dusk.topOfStack->y>=0&&dusk.topOfStack->y<=n
                        &&road[dusk.topOfStack->x-1][dusk.topOfStack->y]==0)
                {
                    dusk.push(dusk.topOfStack->x-1,dusk.topOfStack->y,d[1]);
                    road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
                }
 
                else
                {
                    dusk.topOfStack->d ++;
                }
            }
            if(dusk.topOfStack->d == 5)//如果四个方向都走不通，就出栈
            {
                dusk.pop();
            }
            if(dusk.topOfStack==NULL)//如果到不了
            {
                cout<<"can not arrive"<<endl;
                break;
            }
        }
        dusk.print();//打印
        dusk.Clear();//初始化
        cout<<"please input m and n"<<endl;
    }
 
}

 

　　

 


联系
我们