问题分析
- 用一个二维数组map表示迷宫的信息，其中‘0’表示可以通过，‘1’表示不可通过**，如下图：
在这里插入图片描述 - 对于在一个点上的移动方向，可能是东西南北4方向，或者8方向，如下图：
移动方向 - 用一种方法实现找到从出口的到入口的路径。
实现方法
方向设置
- 我们可以先构建方向结构
，用数组
来表示方向
| q | move[q].a | move[q].b |
|---|---|---|
| N | -1 | 0 |
| NE | -1 | 1 |
| E | 0 | 1 |
| SE | 1 | 1 |
| S | 1 | 0 |
| SW | 1 | -1 |
| W | 0 | -1 |
| NW | -1 | -1 |
- 代码如下：
//方向枚举:东、西、南、北、东北、东南、西北、西南
enum directions{E,W,S,N,NE,SE,NW,SW};
//表示方向
struct offsets
{
int a, b;
};
//构建移动方向move
//设置方向:选择4方向还是8方向
offsets *move_set(int num = 4)
{
/*方向表示表
___________________________
| q | move[q].a | move[q].b |
-----------------------------
| N | -1 | 0 |
| NE| -1 | 1 |
| E | 0 | 1 |
| SE| 1 | 1 |
| S | 1 | 0 |
| SW| 1 | -1 |
| W | 0 | -1 |
| NW| -1 | -1 |
-----------------------------
*/
offsets* move = new offsets[num];
if (num == 4||num==8)
{
move[N].a = -1;
move[N].b = 0;
move[E].a = 0;
move[E].b = 1;
move[S].a = 1;
move[S].b = 0;
move[W].a = 0;
move[W].b = -1;
}
if (num == 8)
{
move[NE].a = -1;
move[NE].b = 1;
move[SE].a = 1;
move[SE].b = 1;
move[SW].a = 1;
move[SW].b = -1;
move[NW].a = -1;
move[NW].b = -1;
}
return move;
}
路径记录和迷宫地图设置
- 建立一个
结构，它包括位置坐标
以及下一次该点的移动方向
；
- 迷宫地图为二维数组，手动输入，代码如下：
//记录路径
struct Items
{
int x, y, dir;
};
//设置地图
char** map_set(const int width, const int high)
{
char** map = new char* [width];
for (int i = 0; i < width; i++)
{
map[i] = new char[high];
}
for (int i = 0; i < width; i++)
{
for (int j = 0; j < high; j++)
{
cin >> map[i][j];
}
}
return map;
}
寻找路径
- 首先我们要用==栈==数据结构来记录路径信息
，这里之所以用指针是方便后续传参；
- 同时我们构建一个==全为零==的二维数组
来记录是否已经通过该点，比如通过
的点，那么
；
- 话不多说，直接上代码：
//寻找路径
stack<Items>* Path(const int width,const int high,char **map,const char can_pass,const int start_x,const int start_y, const char end_signal,const int move_kind)
{
/*参数说明：
* width:迷宫的长度
* high:迷宫的宽度
* **map:二维迷宫的信息
* can_pass:*map[]中可通过字符
* start_x:起点横坐标
* start_y:起点纵坐标
* end_signal:终点字符标志
* move_kind:4方向移动或8方向移动
*/
//获取方向表示
offsets* move;
move = move_set(move_kind);
//记录走过点的信息
stack<Items>*ways=new stack<Items>;
//记录该点是否走过
int** mark = new int* [width];
for (int i = 0; i < width; i++)
{
mark[i] = new int[high];
for (int j = 0; j < high; j++)
{
mark[i][j] = 0;
}
}
//获取起始点
mark[start_x][start_y] = 1;
Items temp;
temp.x = start_x;
temp.y = start_y;
temp.dir = E;
ways->push(temp);
//开始寻找路径
while (!ways->empty())
{
temp = ways->top();
ways->pop();
int i = temp.x, j = temp.y, d = temp.dir;
while (d < move_kind)
{
int g = i + move[d].a, h = j + move[d].b;
if ((g >= 0 && h >= 0) && (g < width && h < high))
{
if (map[g][h] == end_signal)
{
cout << "exist!" << endl;
// 存储最后一次路径信息
Items temp1;
temp1.x = i;
temp1.y = j;
temp1.dir = E;
ways->push(temp1);
return ways;
}
//可以通过，存储该点
if (map[g][h] == can_pass && mark[g][h]==0)
{
mark[g][h] = 1;
temp.x = i;
temp.y = j;
temp.dir = d + 1;
ways->push(temp);
i = g;
j = h;
d = E;
}
else d++;
}
else d++;
}
}
cout << "not exist!" << endl;
return ways;
}
代码总览
#include<iostream>
#include<stack>
using namespace std;
//方向枚举:东、西、南、北、东北、东南、西北、西南
enum directions{E,W,S,N,NE,SE,NW,SW};
//表示方向
struct offsets
{
int a, b;
};
//构建移动方向move
//设置方向:选择4方向还是8方向
offsets *move_set(int num = 4)
{
/*方向表示表
___________________________
| q | move[q].a | move[q].b |
-----------------------------
| N | -1 | 0 |
| NE| -1 | 1 |
| E | 0 | 1 |
| SE| 1 | 1 |
| S | 1 | 0 |
| SW| 1 | -1 |
| W | 0 | -1 |
| NW| -1 | -1 |
-----------------------------
*/
offsets* move = new offsets[num];
if (num == 4||num==8)
{
move[N].a = -1;
move[N].b = 0;
move[E].a = 0;
move[E].b = 1;
move[S].a = 1;
move[S].b = 0;
move[W].a = 0;
move[W].b = -1;
}
if (num == 8)
{
move[NE].a = -1;
move[NE].b = 1;
move[SE].a = 1;
move[SE].b = 1;
move[SW].a = 1;
move[SW].b = -1;
move[NW].a = -1;
move[NW].b = -1;
}
return move;
}
//记录路径
struct Items
{
int x, y, dir;
};
//设置地图
char** map_set(const int width, const int high)
{
char** map = new char* [width];
for (int i = 0; i < width; i++)
{
map[i] = new char[high];
}
for (int i = 0; i < width; i++)
{
for (int j = 0; j < high; j++)
{
cin >> map[i][j];
}
}
return map;
}
//寻找路径
stack<Items>* Path(const int width,const int high,char **map,const char can_pass,const int start_x,const int start_y, const char end_signal,const int move_kind)
{
/*参数说明：
* width:迷宫的长度
* high:迷宫的宽度
* **map:二维迷宫的信息
* can_pass:*map[]中可通过字符
* start_x:起点横坐标
* start_y:起点纵坐标
* end_signal:终点字符标志
* move_kind:4方向移动或8方向移动
*/
//获取方向表示
offsets* move;
move = move_set(move_kind);
//记录走过点的信息
stack<Items>*ways=new stack<Items>;
//记录该点是否走过
int** mark = new int* [width];
for (int i = 0; i < width; i++)
{
mark[i] = new int[high];
for (int j = 0; j < high; j++)
{
mark[i][j] = 0;
}
}
//获取起始点
mark[start_x][start_y] = 1;
Items temp;
temp.x = start_x;
temp.y = start_y;
temp.dir = E;
ways->push(temp);
//开始寻找路径
while (!ways->empty())
{
temp = ways->top();
ways->pop();
int i = temp.x, j = temp.y, d = temp.dir;
while (d < move_kind)
{
int g = i + move[d].a, h = j + move[d].b;
if ((g >= 0 && h >= 0) && (g < width && h < high))
{
if (map[g][h] == end_signal)
{
cout << "exist!" << endl;
// 存储最后一次路径信息
Items temp1;
temp1.x = i;
temp1.y = j;
temp1.dir = E;
ways->push(temp1);
return ways;
}
//可以通过，存储该点
if (map[g][h] == can_pass && mark[g][h]==0)
{
mark[g][h] = 1;
temp.x = i;
temp.y = j;
temp.dir = d + 1;
ways->push(temp);
i = g;
j = h;
d = E;
}
else d++;
}
else d++;
}
}
cout << "not exist!" << endl;
return ways;
}
//打印地图且在地图中显示路径
void Show_path(const int width,const int high,char** map, stack<Items>* ways)
{
if (ways->empty())return;
while (!ways->empty())
{
int x = ways->top().x, y = ways->top().y;
map[x][y] = '@';
ways->pop();
}
for (int i = 0; i < width; i++)
{
for (int j = 0; j < high; j++)
{
cout << map[i][j] << "\t";
}
cout << "\n";
}
}
int main()
{
/*测试数据:(
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
*/
int width, high;
cout << "输入迷宫的长和宽：" << endl;
cin >> width >> high;
char** map;
cout << "输入迷宫信息:" << endl;
map = map_set(width, high);
stack<Items>* ways;
ways = Path(width, high, map, '.', 0, 1, 'G', 4);
Show_path(width, high, map, ways);
return 0;
}
上一节：数据结构-栈与队列--队列
