向大家道歉,之前由于我的个人原因,代码中间出现了一些错误,由于时间长,没有及时更改,今天专门检查了一下并且看了评论发现自己之前的代码的确存在问题,谢谢大家的指正,现将改正后代码贴上,如有问题请及时指正。感谢!!!
问题描述
定义一个二维数组:
int maze[5][5] = {0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
思路(DFS寻路)首先将迷宫存在一个二位数组中,然后遍历数组,遇到1则改变方向,遇到0接着向下走,将此点存入栈中,如果无路,则返回上一结点,将此结点移出栈,并将此点的数组值更改为1,防止死循环。直至找到出口。struct path
{
int x; //横座标
int y; //纵座标
struct path *next;
};
typedef struct Link
{
struct path *head;
}link;
//此处已将队列更换为栈,因为之前的队列删除尾节点会将队列结构完全破坏,而造成队列不能正确工作,sorry!!!
//模拟为栈
void push(link *que, int x, int y)
{
struct path *p;
p = (struct path*)malloc(sizeof(st