1、题目描述
题目链接:迷宫问题
、
注意不能斜着走!
2、题目分析
(1)0为可以走,1不能走且只有唯一一条通路
(2)我们可以通过判断上下左右来确定路是否能通过,再设置如果走过的路就用 2 来标记,这样就不会走回头路了,如果有多条能通过,只选择一条路来走
(3)当我们遇到死胡同时,应该返回到上一个位置,再重新判断其他路是否可以走,没有就继续往回退,直到找到下一条路来,像这样的我们就要用到递归了。
(4)因为坐标是2个数据所以我们创建一个结构体来记录坐标。
(5)我们在一进到函数就先保存坐标,再找其他的路,如果没有找到就说明这是一条死胡同,我们就要往后退,再这个过程我们还需要将进来保存的坐标给拿出来,这种后进先出的的数据结构是栈,所以我们要借助栈来实现,不懂栈的可以看看哦:栈
(6)因为栈是先进后出的,所以这跟题目要求不符合,所以我们要再创建一个栈,将另一个栈的数据倒到新的栈里,再输出就符合题目要求了
(7)注意:输出的格式、在结尾还要释放栈和创建的数组、题目可能要求多组测试用例
3、代码实现
#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//定义结构体,标记坐标
typedef struct Postion {
int row;//行
int col;//列
} PT;
///
//栈
typedef PT STDataType;//结构体类型
typedef struct Stack {
STDataType* a;
int top;//元素个数
int capacity;//空间大小
} ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps) {
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL) {
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
void StackDestory(ST* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x) {
assert(ps);
// 满了-》增容
if (ps->top == ps->capacity) {
STDataType* tmp = (STDataType*)realloc(ps->a,
ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
// 出栈
void StackPop(ST* ps) {
assert(ps);
// 栈空了,调用Pop,直接中止程序报错
assert(ps->top > 0);
//ps->a[ps->top - 1] = 0;
ps->top--;
}
STDataType StackTop(ST* ps) {
assert(ps);
// 栈空了,调用Top,直接中止程序报错
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps) {
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
///
ST Pata;//栈
//判断是否有路
bool IsPass(int** maze, int N, int M, PT pos) {
//(1)判断是否越界
//(2)判断坐标是否为0
if (pos.row >= 0 && pos.row < N
&& pos.col >= 0 && pos.col < M
&& maze[pos.row][pos.col] == 0
) {
return true;
}
else {
return false;
}
}
//打印
void PrintPatar(ST*pata) {
//再设置一个栈
ST patar;
StackInit(&patar);
//将pata这个栈倒到patar栈里
while (!StackEmpty(pata)) {
StackPush(&patar, StackTop(pata));
StackPop(pata);
}
while (!StackEmpty(&patar)) {
PT top = StackTop(&patar);
printf("(%d,%d)\n", top.row, top.col);//按照题目的要求打印
StackPop(&patar);
}
//释放
StackDestory(&patar);
}
bool GetMazePath(int** maze, int N, int M, PT cur) {
//先入栈
StackPush(&Pata, cur);
//改变当前位置
maze[cur.row][cur.col] = 2;
//判断是否到出口
if (cur.row == N - 1 && cur.col == M - 1)
return true;
//接下来我们分上下左右判断是否有路可走
//上
//记录上的位置
PT next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next)) {
//有就进行递归
if (GetMazePath(maze, N, M, next))
//真的有路就返回真即可
return true;
}
//下
//记录下的位置
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next)) {
if (GetMazePath(maze, N, M, next))
return true;
}
//左
//记录左的位置
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next)) {
if (GetMazePath(maze, N, M, next))
return true;
}
//右
//记录右的位置
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next)) {
if (GetMazePath(maze, N, M, next))
return true;
}
StackPop(&Pata);
//走到没路了就返回假
return false;
}
int main() {
int N = 0, M = 0;//行和列的大小
while (scanf("%d%d", &N, &M) != EOF) {//可能会有多组测试用例
//内存函数造一个二维数组
int** maze = (int**)malloc(sizeof(int*) * N);
for (int i = 0; i < N; i++)
maze[i] = (int*)malloc(sizeof(int) * M);
//输入迷宫,0代表可过,1代表不通
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &maze[i][j]);
}
}
//初始化,入口
PT S = { 0, 0 };
//初始化栈
StackInit(&Pata);
//实行
GetMazePath(maze, N, M, S);
//打印
PrintPatar(&Pata);
//释放栈
StackDestory(&Pata);
//释放空间
for (int i = 0; i < N; i++)
free(maze[i]);
free(maze);
maze = NULL;
}
return 0;
}
递归过程:
假设迷宫:
这就是走整个迷宫的流程文章来源:https://www.toymoban.com/news/detail-761174.html
以上就是我的分享了,如果有什么错误,欢迎在评论区留言。
最后,谢谢大家的观看!文章来源地址https://www.toymoban.com/news/detail-761174.html
到了这里,关于数据结构-迷宫问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!