提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

百度美团笔试题——迷宫问题，进来测测数据结构和C语言是否过关

C语言百度数据结构美团 是否 笔试 迷宫 问题
2023-09-11 14:20:37 时间


在这里插入图片描述

一份微语报，众览天下事！
【今日要闻】
中科大：
汽车锂电池突破六分钟充电60%
【今日微语】
再长的路
一步一步走也能走完
再短的路
不迈开双脚也无法到达

让我们进入今天的学习吧！
💪Keep  trying💪

在这里插入图片描述

文章目录

在这里插入图片描述

🍎一、题目详情

在这里插入图片描述
在这里插入图片描述在这里插入图片描述

🍏二、题目分析

  我们简单的提取一下该题的题意：本题要求，输入行N和列M以及二维数组，二维数组内，0代表可以走的路，1代表墙壁，即不能走。迷宫的起点为左上角，终点为右下角，迷宫有且只有一条通路。我们的目的就是：将这条唯一的通路找到并打印到屏幕上。
  大体思路：这里我们采用试探法，也就是，从起点开始，我们在当前点的上下左右四个方向上进行试探，看看是否有方向可以通，如果有方向可以通，那么我们递归调用自己，以这个可以通的方向的坐标点作为递归的起点，再探测这个新的起点的上下左右四个方向。为了避免回到刚走过来的那个点，我们在探测的过程中需要将已经走过的路置为2（只要不是0和1都可以）。当探测到四个方向都不可以通也就是遇到死路时，我们就开始回溯，回到上一个点继续探测剩余没有探测的方向，当探测到了终点时，说明我们找到了通路，直接返回即可。

🍓三、代码步骤分析

🍕3.1 动态开辟数组并输入数据

    首先我们需要开辟出这个存放迷宫的二维数组。由于不是所有的编译器都支持变长数组，所以这里我们动态开辟，适合所有的编译器。
代码如下：

//测试数组的输出
void Print(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main()
{
	int N = 0;//定义行
	int M = 0;//定义列
	while (scanf("%d%d", &N, &M) != EOF)//输入行列,利用while，不止读取一条
	{
		//动态开辟数组
		int** maze = (int**)malloc(sizeof(int*)*N);//开辟的行数
		//开辟每行的元素个数
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		//输入二维数组
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}
		//测试：打印二维数组
		Print(maze,N,M);
	//......
	//......
		//释放动态开辟的空间
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		maze = NULL;
	}
	return 0;
}

这里我们可以先测试一下二维数组是否能正常输入输出，确认正常再继续往下写。

🍖3.2 定义坐标结构体

   由于后面所有的点都是坐标，所以我们直接定义一个结构体，方便后面使用，定义结构体的代码如下：

//定义坐标位置的结构体
typedef struct Position
{
	int row;//行
	int col;//列
}PT;

🍟3.3 判断下一步是否可通

   按照需求，我们需要独立封装一个函数IsPass，这个函数的作用是判断下一步是否可以继续走，也就是是否遇到死路了，横纵坐标不越界并且不是墙就可以通。代码如下：

//判断是否能通
bool IsPass(int** maze, int N, int M, PT cur)
{
	if (cur.row >= 0 && cur.row < N&&
		cur.col >= 0 && cur.col < M&&
		maze[cur.row][cur.col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

🍡3.4 寻找通路：GetMazePath

   做完了上面的几步，我们就可以开始写我们本题的核心代码了，寻找通路的函数，我们单独封装成一个函数GetMazePath。当我们在某个方向找到通路之后，就不需要继续找其方向了，所以这里我们采取bool类型的返回值，找到终点后直接返回true；由于我们最终目的是输出路径到屏幕上，所以我们必须将走过的路径存起来，这里我们采取数据结构里面的栈来存储（由于C语言没有STL，所以栈需要我们手动实现，后面会给出代码）。进入函数的第一步我们必须将当前位置压入栈里面，存储起来；由于我们需要用到递归，所以我们必须指明递归结束的条件，也就是，如果走到了出口，就返回true；然后我们开始在四个方向上进行探测，探测之前我们需要将走过的路置为2；如果四个方向探测完，都没进去递归，说明找到了死路，此时我们就需要开始回溯，回溯之前，我们必须将当前位置出栈，因为这条路不可能是最终路径了，然后我们需要返回FALSE；

//寻找通路
bool GetMazePath(int** maze, int N, int M, PT cur)
{
	//现将当前位置入栈
	StackPush(&path, cur);

	//如果走到出口返回真
	if (cur.row == N - 1 && cur.col == M - 1)
	{
		return true;
	}
	//探测当前位置的上下左右四个方向
	PT next;
	//把走过的路径置为2，避免走回头路
	maze[cur.row][cur.col] = 2;

	//探测上
	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(&path);
	return false;
}

🍿3.5 打印路径

   经过第四步，我们的栈里面已经存储好了通路的路径，按道理我们直接打印这个栈里面的内容就可以了。但细心的小伙伴应该可以发现，由于栈后进先出的特性，所以打印出来的通路正好是个反的，为了解决这个问题，我们需要再借助一个栈，将数据倒一下再输出，代码如下：

//输出路径坐标
void PrintPath(ST* path)
{
	//新建一个栈rpath将path倒到rpath
	ST rpath;
	StackInit(&rpath);
	while (!StackEmpty(path))
	{
		StackPush(&rpath, StackTop(path));
		StackPop(path);
	}

	//输出rpath
	while (!StackEmpty(&rpath))
	{
		PT top = StackTop(&rpath);
		printf("(%d,%d)\n", top.row, top.col);
		StackPop(&rpath);
	}

	StackDestory(&rpath);

}

🍤3.6 栈的代码

stack.h==

typedef PT STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDateType x);
//出栈
void StackPop(ST* ps);
//取出栈顶元素
STDateType StackTop(ST* ps);
//获取当前栈大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);

stack.c

//初始化
void StackInit(ST* ps)
{
	ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
		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);
	assert(ps->top > 0);
	ps->top--;
}

//获取栈顶元素
STDateType StackTop(ST* ps)
{
	assert(ps);
	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;
}

🍑四、完整代码

🍕4.1 C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义坐标位置的结构体
typedef struct Position
{
	int row;//行
	int col;//列
}PT;

//栈的代码
typedef PT STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDateType x);
//出栈
void StackPop(ST* ps);
//取出栈顶元素
STDateType StackTop(ST* ps);
//获取当前栈大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);



//初始化
void StackInit(ST* ps)
{
	ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
		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);
	assert(ps->top > 0);
	ps->top--;
}

//获取栈顶元素
STDateType StackTop(ST* ps)
{
	assert(ps);
	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;
}
/


//测试数组的输出
void Print(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

//输出路径坐标
void PrintPath(ST* path)
{
	//新建一个栈rpath将path倒到rpath
	ST rpath;
	StackInit(&rpath);
	while (!StackEmpty(path))
	{
		StackPush(&rpath, StackTop(path));
		StackPop(path);
	}

	//输出rpath
	while (!StackEmpty(&rpath))
	{
		PT top = StackTop(&rpath);
		printf("(%d,%d)\n", top.row, top.col);
		StackPop(&rpath);
	}

	StackDestory(&rpath);

}


//判断是否能通
bool IsPass(int** maze, int N, int M, PT cur)
{
	if (cur.row >= 0 && cur.row < N&&
		cur.col >= 0 && cur.col < M&&
		maze[cur.row][cur.col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//定义一个全局的栈，用来存储路径
ST path;

//寻找通路
bool GetMazePath(int** maze, int N, int M, PT cur)
{
	//现将当前位置入栈
	StackPush(&path, cur);

	//如果走到出口返回真
	if (cur.row == N - 1 && cur.col == M - 1)
	{
		return true;
	}
	//探测当前位置的上下左右四个方向
	PT next;
	//把走过的路径置为2，避免走回头路
	maze[cur.row][cur.col] = 2;

	//探测上
	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(&path);
	return false;
}


int main()
{
	int N = 0;//定义行
	int M = 0;//定义列
	while (scanf("%d%d", &N, &M) != EOF)//输入行列,利用while，不止读取一条
	{
		//动态开辟数组
		int** maze = (int**)malloc(sizeof(int*)*N);//开辟的行数
		//开辟每行的元素个数
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		//输入二维数组
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		//测试：打印二维数组
		//Print(maze,N,M);

		//寻找通路
		//开始找通路前先将栈初始化
		StackInit(&path);
		PT entry = { 0,0 };
		if (GetMazePath(maze, N, M, entry))
		{
			//printf("找到通路！\n");
			PrintPath(&path);
		}
		else
		{
			printf("没有通路！\n");
		}
		//找完通路后将栈销毁
		StackDestory(&path);

		//释放动态开辟的空间
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		maze = NULL;
	}
	return 0;
}

🍖4.2 C++实现

#include<iostream>
using namespace std;
#include<stack>

//定义坐标位置的结构体
typedef struct Position
{
	int row;//行
	int col;//列
}PT;


//测试数组的输出
void Print(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

//输出路径坐标
void PrintPath(stack<PT> path)
{
	//新建一个栈rpath将path倒到rpath
	stack<PT> rpath;
	while (!path.empty())
	{
		rpath.push(path.top());
		path.pop();
	}

	//输出rpath
	while (!rpath.empty())
	{
		PT top = rpath.top();
		printf("(%d,%d)\n", top.row, top.col);
		rpath.pop();
	}

}


//判断是否能通
bool IsPass(int** maze, int N, int M, PT cur)
{
	if (cur.row >= 0 && cur.row < N&&
		cur.col >= 0 && cur.col < M&&
		maze[cur.row][cur.col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//定义一个全局的栈，用来存储路径
stack<PT> path;

//寻找通路
bool GetMazePath(int** maze, int N, int M, PT cur)
{
	//现将当前位置入栈
	path.push(cur);

	//如果走到出口返回真
	if (cur.row == N - 1 && cur.col == M - 1)
	{
		return true;
	}
	//探测当前位置的上下左右四个方向
	PT next;
	//把走过的路径置为2，避免走回头路
	maze[cur.row][cur.col] = 2;

	//探测上
	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;
		}
	}

	//将当前位置出栈
	path.pop();
	return false;
}


int main()
{
	
	int N = 0;//定义行
	int M = 0;//定义列
	while (scanf("%d%d", &N, &M) != EOF)//输入行列,利用while，不止读取一条
	{
		//动态开辟数组
		int** maze = (int**)malloc(sizeof(int*)*N);//开辟的行数
		//开辟每行的元素个数
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		//输入二维数组
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		//测试：打印二维数组
		//Print(maze,N,M);

		//寻找通路

		PT entry = { 0,0 };
		if (GetMazePath(maze, N, M, entry))
		{
			//printf("找到通路！\n");
			PrintPath(path);
		}
		else
		{
			printf("没有通路！\n");
		}

		//释放动态开辟的空间
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		maze = NULL;
	}
	return 0;
}

C++利用STL里面的栈，可以比较轻松的实现本题。

🍉五、进阶版——地下迷宫

🍕5.1 题目描述

在这里插入图片描述在这里插入图片描述

🍖2.2 提纲挈领

   对比第一题，本题有几个不同的点，第一个是终点变成了右上角；第二个是不止一条通路；第三个是0代表墙，1代表通路，和上一题正好相反；第四个是加入了体力值，体力值耗尽如果还没有找到通路那么也算失败；第五个输出格式不一样。我们来分析一下，其实这题最重要的点事加入了体力值这个东西，因为给出了多条通路，所以我们想要在有限的体力值内走出去，我们是不是就要找到最短的那条通路，如果说最短的通路体力值都不够的话，那么这个题就无解。
6.3 需要改动的地方
   我们从上一题的代码上直接改动，先改动简单易改的点，首先，因为我们要找出最短的通路，所以，我们必须把所有的通路全部找出来，而不是像上题一样，找到一条通路就返回，所以这里我们的返回值不能再是bool型了，而是不要返回值，所以我们需要把所有rerun和if判断的代码给它去掉；如下图所示：
在这里插入图片描述
把所有打×的地方全部删掉，其他三个方向也是一样。
然后我们需要新增体力值并实现体力值的消耗，如下图所示：
在这里插入图片描述在这里插入图片描述

改变墙和通路：

在这里插入图片描述
改终点：
在这里插入图片描述
改变输出格式：
在这里插入图片描述
当把所有的这些点改完之后，我们其实可以通过一部分的测试用例了，说明我们的逻辑是对的，但唯一的问题就是，现在还不是最短路径，我们现在要找出最短路径，怎么找？很简单，我们需要再借助一个栈minpath，用来存储最短路径，代码的改动就在我们的递归结束条件里面，如果找到了通路并且比之前的通路要短并且还有体力，我们就更新一下minpath，代码如下：

//如果走到出口还有体力，更新路径
	if (cur.row == 0 && cur.col == M - 1 && p >= 0)
	{
		//更新最短路径
		if (StackEmpty(&minpath) ||
			StackSize(&minpath) > StackSize(&path))
		{
			//为了避免浅拷贝，我们这里现将之前的minpath释放
			StackDestory(&minpath);
			//将path的数据拷贝到minpath中
			StackCopy(&minpath, &path);
		}
	}

这里的StackCopy(&minpath, &path);我们需要单独的实现一下：

//拷贝栈中的元素
void StackCopy(ST* pcopy, ST* ppath)
{
	pcopy->a = (STDateType*)malloc(sizeof(STDateType*)*ppath->top);
	memcpy(pcopy->a, ppath->a, sizeof(STDateType*)*ppath->top);
	pcopy->top = ppath->top;
	pcopy->capacity = ppath->capacity;
}

最后我们只需要在main函数里面正常输出通路即可

🍐六、进阶版——地下迷宫完整代码

🍕6.1 C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>

//定义坐标位置的结构体
typedef struct Position
{
	int row;//行
	int col;//列
}PT;

//栈的代码
typedef PT STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDateType x);
//出栈
void StackPop(ST* ps);
//取出栈顶元素
STDateType StackTop(ST* ps);
//获取当前栈大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);



//初始化
void StackInit(ST* ps)
{
	ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
		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);
	assert(ps->top > 0);
	ps->top--;
}

//获取栈顶元素
STDateType StackTop(ST* ps)
{
	assert(ps);
	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;
}

//拷贝栈中的元素
void StackCopy(ST* pcopy, ST* ppath)
{
	pcopy->a = (STDateType*)malloc(sizeof(STDateType*)*ppath->top);
	memcpy(pcopy->a, ppath->a, sizeof(STDateType*)*ppath->top);
	pcopy->top = ppath->top;
	pcopy->capacity = ppath->capacity;
}
/


//测试数组的输出
void Print(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

//输出路径坐标
void PrintPass(ST* path)
{
	//将pass倒到rpass
	ST rpath;
	StackInit(&rpath);
	while (!StackEmpty(path))
	{
		StackPush(&rpath, StackTop(path));
		StackPop(path);
	}

	//输出rpath
	while (!StackEmpty(&rpath))
	{
		PT top = StackTop(&rpath);
		printf("[%d,%d]", top.row, top.col);
		if (StackSize(&rpath) > 1)
		{
			printf(",");
		}
		StackPop(&rpath);
	}

	StackDestory(&rpath);

}


//判断是否能通
bool IsPass(int** maze, int N, int M, PT cur)
{
	if (cur.row >= 0 && cur.row < N&&
		cur.col >= 0 && cur.col < M&&
		maze[cur.row][cur.col] == 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//定义一个栈，用来存储路径
ST path;
//再定义一个栈，用来存储最小路径
ST minpath;

//寻找通路
void GetMazePath(int** maze, int N, int M, PT cur, int p)
{
	//现将当前位置入栈
	StackPush(&path, cur);

	//如果走到出口还有体力，更新路径
	if (cur.row == 0 && cur.col == M - 1 && p >= 0)
	{
		//更新最短路径
		if (StackEmpty(&minpath) ||
			StackSize(&minpath) > StackSize(&path))
		{
			//为了避免浅拷贝，我们这里现将之前的minpath释放
			StackDestory(&minpath);
			//将path的数据拷贝到minpath中
			StackCopy(&minpath, &path);
		}
	}
	//探测当前位置的上下左右四个方向
	PT next;
	//把走过的路径置为2，避免走回头路
	maze[cur.row][cur.col] = 2;

	//探测上
	next = cur;
	next.row -= 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 3);
	}

	//探测下
	next = cur;
	next.row += 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p);
	}

	//探测左
	next = cur;
	next.col -= 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 1);
	}

	//探测右
	next = cur;
	next.col += 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 1);
	}

	//回溯的过程中改回标记为1
	maze[cur.row][cur.col] = 1;
	//如果四个方向都不通，将当前位置出栈
	StackPop(&path);
}


int main()
{
	int N = 0;//定义行
	int M = 0;//定义列
	int P = 0;//定义体力值
	while (scanf("%d%d%d", &N, &M, &P) != EOF)//输入行列,利用while，不止读取一条
	{
		//动态开辟数组
		int** maze = (int**)malloc(sizeof(int*)*N);//开辟的行数
		//开辟每行的元素个数
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		//输入二维数组
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		//测试：打印二维数组
		//Print(maze,N,M);

		//寻找通路
		StackInit(&path);//初始化栈
		StackInit(&minpath);
		PT entry = { 0,0 };//定义入口
		GetMazePath(maze, N, M, entry, P);

		//打印路径
		if (!StackEmpty(&minpath))
		{
			PrintPass(&minpath);
		}
		else
		{
			printf("Can not escape!");
		}

		StackDestory(&path);
		StackDestory(&minpath);

		//释放动态开辟的空间
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		maze = NULL;
	}
	return 0;
}

🍖6.2 C++实现

#include<iostream>
using namespace std;
#include<stack>

//定义坐标位置的结构体
typedef struct Position
{
	int row;//行
	int col;//列
}PT;


//测试数组的输出
void Print(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

//输出路径坐标
void PrintPath(stack<PT> path)
{
	//新建一个栈rpath将path倒到rpath
	stack<PT> rpath;
	while (!path.empty())
	{
		rpath.push(path.top());
		path.pop();
	}

	//输出rpath
	while (!rpath.empty())
	{
		PT top = rpath.top();
		printf("[%d,%d]", top.row, top.col);
		if (rpath.size() > 1)
		{
			printf(",");
		}
		rpath.pop();
	}

}


//判断是否能通
bool IsPass(int** maze, int N, int M, PT cur)
{
	if (cur.row >= 0 && cur.row < N&&
		cur.col >= 0 && cur.col < M&&
		maze[cur.row][cur.col] == 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//定义一个全局的栈，用来存储路径
stack<PT> path;
//再定义一个栈，用来存储最小路径
stack<PT> minpath;

//寻找通路
void GetMazePath(int** maze, int N, int M, PT cur, int p)
{
	//现将当前位置入栈
	path.push(cur);

	//如果走到出口返回真
	if (cur.row == 0 && cur.col == M - 1 && p >= 0)
	{
		minpath = path;
	}
	//探测当前位置的上下左右四个方向
	PT next;
	//把走过的路径置为2，避免走回头路
	maze[cur.row][cur.col] = 2;

	//探测上
	next = cur;
	next.row -= 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 3);

	}

	//探测下
	next = cur;
	next.row += 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p);

	}

	//探测左
	next = cur;
	next.col -= 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 1);

	}

	//探测右
	next = cur;
	next.col += 1;
	if (IsPass(maze, N, M, next))
	{
		//如果能通，则以当前点为起点递归
		GetMazePath(maze, N, M, next, p - 1);

	}

	//回溯的过程中改回标记为1
	maze[cur.row][cur.col] = 1;
	//将当前位置出栈
	path.pop();
}


int main()
{

	int N = 0;//定义行
	int M = 0;//定义列
	int P = 0;//定义体力值
	while (scanf("%d%d%d", &N, &M, &P) != EOF)//输入行列,利用while，不止读取一条
	{
		//动态开辟数组
		int** maze = (int**)malloc(sizeof(int*)*N);//开辟的行数
		//开辟每行的元素个数
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		//输入二维数组
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		//测试：打印二维数组
		//Print(maze,N,M);

		//寻找通路

		PT entry = { 0,0 };
		GetMazePath(maze, N, M, entry, P);

		if (!minpath.empty())
		{
			PrintPath(minpath);
		}
		else
		{
			printf("Can not escape!");
		}


		//释放动态开辟的空间
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		maze = NULL;
	}
	return 0;
}

         👆回到顶部👆

在这里插入图片描述

相关文章