问题分析
- 求一点到另一点的最短距离，比如下图中，绿点到黄点的最短路径的数值，蓝格子可以通过，白色格子不可通过：
-
最终呈现效果如下图：
实现方法
- 前面一大部分与上一节提到的迷宫问题类似（详情见：数据结构-栈与队列--迷宫问题）
- 我们在寻找路径的
函数上稍作修改就可以了，其中加上
来记录到达该点的步数，代码如下：
//寻找路径
void 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)
{
/*参数说明：
* high:迷宫的长度
* width:迷宫的宽度
* **map:二维迷宫的信息
* can_pass:**map中可通过字符
* start_x:起点横坐标
* start_y:起点纵坐标
* end_signal:终点字符标志
* move_kind:4方向移动或8方向移动
*/
//获取方向表示
offsets* move;
move = move_set(move_kind);
//记录走过点的信息
queue<Items>ways;
//记录该点是否走过
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.count = 0;
ways.push(temp);
//其实点至该点的长度
int cross_num = 0;
//开始寻找路径
while (!ways.empty())
{
temp = ways.front();
ways.pop();
cross_num = temp.count;
int i = temp.x, j = temp.y,d=E;
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 << cross_num+1 << endl;
return;
}
if (map[g][h] == can_pass && mark[g][h] == 0)
{
mark[g][h] = 1;
temp.x = g;
temp.y = h;
temp.count = cross_num+1;
ways.push(temp);
d++;
}
else d++;
}
else d++;
}
}
//未找到路径
cout<<-1<<endl;
}
代码总览
#include<iostream>
#include<queue>
using namespace std;
//方向枚举:东、西、南、北、东北、东南、西北、西南
enum directions { E, W, S, N, NE, SE, NW, SW };
//表示方向
struct offsets
{
int a, b;
};
//记录路径
struct Items
{
int x, y, count;
};
//构建移动方向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)
{
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;
}
//设置地图
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;
}
//寻找路径
void 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)
{
/*参数说明：
* high:迷宫的长度
* width:迷宫的宽度
* **map:二维迷宫的信息
* can_pass:**map中可通过字符
* start_x:起点横坐标
* start_y:起点纵坐标
* end_signal:终点字符标志
* move_kind:4方向移动或8方向移动
*/
//获取方向表示
offsets* move;
move = move_set(move_kind);
//记录走过点的信息
queue<Items>ways;
//记录该点是否走过
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.count = 0;
ways.push(temp);
//其实点至该点的长度
int cross_num = 0;
//开始寻找路径
while (!ways.empty())
{
temp = ways.front();
ways.pop();
cross_num = temp.count;
int i = temp.x, j = temp.y,d=E;
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 << cross_num+1 << endl;
return;
}
if (map[g][h] == can_pass && mark[g][h] == 0)
{
mark[g][h] = 1;
temp.x = g;
temp.y = h;
temp.count = cross_num+1;
ways.push(temp);
d++;
}
else d++;
}
else d++;
}
}
//未找到路径
cout<<-1<<endl;
}
int main()
{
/*测试数据:
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
*/
int width, high;
cout << "请输入迷宫的长与宽：" << endl;
cin >> width >> high;
char** map;
cout << "请输入迷宫信息：" << endl;
map = map_set(width, high);
Path(width, high, map, '.', 0, 1, 'G', 4);
return 0;
}
上一节：数据结构-栈与队列--迷宫问题
