《数据结构、算法与应用C++语言描述》-栈的应用-迷宫老鼠问题

迷宫老鼠

完整可运行代码见：Github::Data-Structures-Algorithms-and-Applications/_13Maze_mouse/

问题描述

迷宫（如图 8-9 所示）是一个矩形区域，有一个入口和一个出口。迷宫内部包含不能穿越的墙壁或障碍物。这些障碍物沿着行和列放置，与迷宫的边界平行。迷宫的入口在左上角，出口在右下角。

假定用 nxm 的矩阵来描述迷宫，矩阵的位置（1，1）表示入口，（n，m）表示出口，n 和m分别代表迷宫的行数和列数。迷宫的每个位置都可用其行号和列号表示。在矩阵中，当且仅当在位置（i，j）处有一个障碍时，其值为 1，否则其值为 0。图 8-10 给出了图8-9 中的迷宫所对应的矩阵表示。迷宫老鼠（rat in a maze）问题是要寻找一条从入口到出口的路径。路径是一个由位置组成的序列，每一个位置都没有障碍，而且除入口之外，路径上的每个位置都是前一个位置在东、南、西或北方向上相邻的一个位置（如图8-11 所示）。

我们要编写程序来解决迷宫老鼠问题。假设迷宫是一个方阵（即m=n）且足够小，能够整个存储在目标计算机的内存中。程序应是独立的，一个用户可以输入自己选择的迷宫来直接寻找迷宫路径。

求解策略

逻辑：首先把迷宫的入口作为当前位置。如果当前位置是迷宫出口，那么已经找到了一条路径，寻找工作结束。如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以阻止寻找过程又绕回到这个位置。然后检查相邻位置是否有空闲（即没有障碍物），如果有，就移动到一个空闲的相邻位置上，然后从这个位置开始寻找通往出口的路径。如果不成功，就选择另一个空闲的相邻位置，并从它开始寻找通往出口的路径。为了方便移动，在进入新的相邻位置之前，把当前位置保存在一个栈中。如果所有空闲的相邻位置都已经被探索过，但还未能找到路径，则表明迷宫不存在从入口到出口的路径。

路径的表示：注意，在栈中始终有一条从入口到当前位置的路径。如果最终到达了出口，那么栈中的路径就是从入口到出口的路径。

padding：为了避免在处理内部位置和边界位置时存在差别，可以在迷宫的周围增加一圈障碍物。对于一个mxm的数组maze，这一圈障碍物将占据数组maze的第0行、第m+1行、第0列和第m+1列。

最长路径：一个没有障碍物的 m× m 迷宫，最长的路径可包含$m^2$个位置。

因为路径包含的位置没均不相同，而且迷宫仅有 $m^2$ 个位置，所以一条路径所包含的位置最多不超过 $m^2$。又因为路径的最后一个位置不必存储到栈中，所以在栈中存储的位置最多是$m^2-1$。注意，在一个没有障碍物的迷宫中，在入口和出口之间，总有一条最多包含 2m 个位置的路径。

偏移量表：例如，如果当前位置是（3，4），则其右边相邻位置的行坐标为3+offset[0].row=3，列坐标为 4+offset[0].col=5。

防止走回去：为了不重蹈已经走过的位置，我们在每一个走过的位置maze[i] [j]上设置障碍物。

代码

#include 
#include 
using namespace std;

/*用于存储迷宫地址的结构体*/
struct position
{
    int row,  //行
    col;  //列
    operator int() const { return row; }
    friend ostream& operator<<(ostream& out, const position x)
    {
        out << "(" << x.row << "," << x.col << ")";
        return out;
    }
};

/*创建二维数组*/
template <class T>
bool make2dArray(T**& x, int numberOfRows, int numberOfColumns)
{
    try {
        //行指针
        x = new T * [numberOfRows];
        //为每一行分配内存
        for (int i = 0; i < numberOfRows; i++)
            x[i] = new int[numberOfColumns];
        return true;
    }
    catch (bad_alloc) { return false; }
}

/*遍历二维数组*/
template<class T>
void traverse2dArray(T**& x, int numberOfRows, int numberOfColumns)
{
    for (int i = 0; i < numberOfRows; i++)
    {
        for (int j = 0; j < numberOfColumns; j++)
        {
            cout.width(4);
            cout << x[i][j] << "  ";
        }
        cout << endl;
    }
}

/*迷宫老鼠全局变量*/
int** maze,mazeSize;
stack<position> path;//存储路径的数组栈
/*迷宫老鼠问题*/
/*展示界面*/
void welcome()
{
    cout << "******Welcome To RAT IN A MAZE******" << endl;
    cout << "************Jasmine,2022************" << endl;
}
/*输入迷宫*/
void inputMaze()
{
    cout << "Please enter the size of Maze-Matrix:";
    while (!(cin >> mazeSize))
    {
        cin.clear();//清空标志位
        while (cin.get() != '\n')//删除无效的输入
            continue;
        cout << "Please enter the size of Maze-Matrix:";
    }
    //+2的原因是为了避免在处理内部位置和边界位置时存在差别
    make2dArray<int>(maze, mazeSize + 2, mazeSize + 2);
    //初始化边界位置的数值
    for (int i = 0; i <= mazeSize + 1; i++)
    {
        maze[i][0] = 1;
        maze[0][i] = 1;
        maze[i][mazeSize + 1] = 1;
        maze[mazeSize + 1][i] = 1;
    }
    //初始化迷宫
    for (int i = 1; i <= mazeSize; i++)
        for(int j = 1; j <= mazeSize; j++)
        {
            int positionij;
            cout << "Please enter maze[" << i << "," << j << "]:";
            while (!(cin >> positionij))
            {
                cin.clear();//清空标志位
                while (cin.get() != '\n')//删除无效的输入
                    continue;
                cout << "Please enter maze[" << i << "," << j << "]:";
            }
            maze[i][j] = positionij;
        }
    cout << "The maze = " << endl;
    traverse2dArray<int>(maze, mazeSize + 2, mazeSize + 2);
}
/*寻找迷宫路径入口(1,1),出口(size,size)，如找到返回true，如没找到则返回false*/
bool findPath()
{
    path = stack<position>();//存储路径
    //初始化偏移量
    position offset[4];
    offset[0].row = 0; offset[0].col = 1;//右
    offset[1].row = 1; offset[1].col = 0;//下
    offset[2].row = 0; offset[2].col = -1;//左
    offset[3].row = -1; offset[3].col = 0;//上
    //入口
    position here;
    here.row = 1;
    here.col = 1;
    maze[1][1] = 1;//防止回到入口
    int option = 0;//下一步
    int lastOption = 3;

    //寻找一条路径
    while ((here.row != mazeSize) || (here.col != mazeSize))
    {
        int r, c;
        while (option <= lastOption)
        {
            r = here.row + offset[option].row;
            c = here.col + offset[option].col;
            if (maze[r][c] == 0) break;
            option++;//下一个选择
        }
        // 相邻的下一步是否找到
        if (option <= lastOption)
        {//移到maze[r][c]
            path.push(here);
            here.row = r;
            here.col = c;
            maze[r][c] = 1;//防止重复访问该节点
            option = 0;
        }
        else//如果没找到
        {
            if (path.empty())
                return false;
            position next = path.top();
            path.pop();
            if (here.row == next.row) // 说明是移动的左右
                option = 2 + next.col - here.col; // 如果是左的话，op = 3就是上；如果是右的话，op = 1，就是下
            else // 此时移动的是上下
                option = 3 + next.row - here.row; // 如果是上的话，op = 4；如果是下的话，op = 2，就是左
            here = next;
        }
    }
    path.push(here);
    return true;
}
/*输出迷宫路径*/
void outputPath()
{
    int i = 0;
    cout << "The path = ";
    stack<position> temp;
    while(!path.empty()){
        cout << path.top() << "->";
        temp.push(path.top());
        path.pop();
    }
    while(!temp.empty() && temp.size() > 1){
        cout << temp.top() << "->";
        temp.pop();
    }
    cout << temp.top() << endl;
    temp.pop();
}

int main()
{
    cout << "RAT IN A MAZE********************" << endl;
    welcome();
    inputMaze();
    findPath();
    outputPath();
    return 0;
}
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

运行结果

C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
RAT IN A MAZE********************
******Welcome To RAT IN A MAZE******
************Jasmine,2022************
Please enter the size of Maze-Matrix:3
Please enter maze[1,1]:0
Please enter maze[1,2]:0
Please enter maze[1,3]:0
Please enter maze[2,1]:1
Please enter maze[2,2]:1
Please enter maze[2,3]:0
Please enter maze[3,1]:1
Please enter maze[3,2]:1
Please enter maze[3,3]:0
The maze =
   1     1     1     1     1
   1     0     0     0     1
   1     1     1     0     1
   1     1     1     0     1
   1     1     1     1     1
The path = (3,3)->(2,3)->(1,3)->(1,2)->(1,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)

Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23