問題分析
- 用一個(gè)二維數(shù)組map表示迷宮的信息弱贼，其中‘0’表示可以通過蒸苇，‘1’表示不可通過**，如下圖：
- 對于在一個(gè)點(diǎn)上的移動(dòng)方向吮旅，可能是東西南北4方向溪烤，或者8方向味咳，如下圖：
- 用一種方法實(shí)現(xiàn)找到從出口的到入口的路徑。
實(shí)現(xiàn)方法
方向設(shè)置
- 我們可以先構(gòu)建方向結(jié)構(gòu)
檬嘀，用數(shù)組![offsets\&move[4]或offsets\&move[8]](https://math.jianshu.com/math?formula=offsets%5C%26move%5B4%5D%E6%88%96offsets%5C%26move%5B8%5D)
來表示方向
| 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;
};
//構(gòu)建移動(dòng)方向move
//設(shè)置方向:選擇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;
}
路徑記錄和迷宮地圖設(shè)置
- 建立一個(gè)
結(jié)構(gòu)，它包括位置坐標(biāo)
以及下一次該點(diǎn)的移動(dòng)方向
衷掷；
- 迷宮地圖為二維數(shù)組辱姨，手動(dòng)輸入，代碼如下：
//記錄路徑
struct Items
{
int x, y, dir;
};
//設(shè)置地圖
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;
}
尋找路徑
- 首先我們要用==棧==數(shù)據(jù)結(jié)構(gòu)來記錄路徑信息
)
戚嗅，這里之所以用指針是方便后續(xù)傳參雨涛；
- 同時(shí)我們構(gòu)建一個(gè)==全為零==的二維數(shù)組
)
來記錄是否已經(jīng)通過該點(diǎn)，比如通過
的點(diǎn)懦胞，那么![mark[i][j]=1](https://math.jianshu.com/math?formula=mark%5Bi%5D%5Bj%5D%3D1)
替久；
- 話不多說，直接上代碼：
//尋找路徑
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)
{
/*參數(shù)說明：
* width:迷宮的長度
* high:迷宮的寬度
* **map:二維迷宮的信息
* can_pass:*map[]中可通過字符
* start_x:起點(diǎn)橫坐標(biāo)
* start_y:起點(diǎn)縱坐標(biāo)
* end_signal:終點(diǎn)字符標(biāo)志
* move_kind:4方向移動(dòng)或8方向移動(dòng)
*/
//獲取方向表示
offsets* move;
move = move_set(move_kind);
//記錄走過點(diǎn)的信息
stack<Items>*ways=new stack<Items>;
//記錄該點(diǎn)是否走過
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;
}
}
//獲取起始點(diǎn)
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;
// 存儲(chǔ)最后一次路徑信息
Items temp1;
temp1.x = i;
temp1.y = j;
temp1.dir = E;
ways->push(temp1);
return ways;
}
//可以通過躏尉，存儲(chǔ)該點(diǎn)
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;
};
//構(gòu)建移動(dòng)方向move
//設(shè)置方向:選擇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;
};
//設(shè)置地圖
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)
{
/*參數(shù)說明：
* width:迷宮的長度
* high:迷宮的寬度
* **map:二維迷宮的信息
* can_pass:*map[]中可通過字符
* start_x:起點(diǎn)橫坐標(biāo)
* start_y:起點(diǎn)縱坐標(biāo)
* end_signal:終點(diǎn)字符標(biāo)志
* move_kind:4方向移動(dòng)或8方向移動(dòng)
*/
//獲取方向表示
offsets* move;
move = move_set(move_kind);
//記錄走過點(diǎn)的信息
stack<Items>*ways=new stack<Items>;
//記錄該點(diǎn)是否走過
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;
}
}
//獲取起始點(diǎn)
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;
// 存儲(chǔ)最后一次路徑信息
Items temp1;
temp1.x = i;
temp1.y = j;
temp1.dir = E;
ways->push(temp1);
return ways;
}
//可以通過，存儲(chǔ)該點(diǎn)
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()
{
/*測試數(shù)據(jù):(
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;
}
上一節(jié)：數(shù)據(jù)結(jié)構(gòu)-棧與隊(duì)列--隊(duì)列
