迷宫问题
一.需求设计:
可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的
路径,并将路径输出。
二.概要设计:
存储结构:
采用了数组以及结构体来存储数据,在探索迷宫的过程中用到的栈,属于顺序存储结
构。
//八个方向的数组表示形式
int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-
1, 0},{-1, 1}};
//用结构体表示位置
struct position
{
int x,y;
};
position stack[m*m+1];
基本算法:
走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、
西、西北、北、东北 8 个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,
则前进一步,在新位置上继续进行搜索;如果 8 个方向都走不通或曾经到达过,则退回一
步,在原来的位置上继续试探下一位置。
每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若
退回到了入口处,则说明不存在通路。
用一个字符类型的二维数组表示迷宫,数组中每个元素取值“ 0”(表示通路)或“1”
(表示墙壁)。迷宫的入口点在位置(1,1)处,出口点在位置(m,m)处。设计一个模
拟走迷宫的算法,为其寻找一条从入口点到出口点的通路。
二维数组的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“1”, 表示迷宫的边界;
第 1 行第 1 列元素和第 m 行第 m 列元素置成“0”, 表示迷宫的入口和出口;其余元素值用
随机函数产生。
假设当前所在位置是(x,y)。沿某个方向前进一步,它可能到达的位置最多有 8 个。
如果用二维数组 move 记录 8 个方向上行下标增量和列下标增量,则沿第 i 个方向前进
一步,可能到达的新位置坐标可利用 move 数组确定:
x=x+move[i][0]
y=y+move[i][1]
从迷宫的入口位置开始,沿图示方向顺序依次进行搜索。
在搜索过程中,每前进一步,在所到位置处做标记“”
(表示这个位置在通路上),并将该位置的坐标压入栈中。
每次后退的时候,先将当前所在位置处的通路标记“”改
成死路标记“×”(表示这个位置曾到达过但走不通,以后
不要重复进入),然后将该位置的坐标从栈顶弹出。
评论5