当前位置： 首页 > article >正文

数据结构--迷宫问题

article 2025/2/12 19:50:08

1. 迷宫问题求解
 

迷宫问题_牛客题霸_牛客网

        以上迷宫OJ题曾经是百度某一年的其中一个笔试题，迷宫问题本质就是一个图的遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标，栈记录坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路。

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

// 迷宫坐标结构
typedef struct Position {
	int row;	// 行
	int col;	// 列
}PT;

typedef PT STDataType;

// 栈的结构--建议使用数组
typedef struct Stack {
	STDataType* a;
	int top;	// 栈顶
	int capacity;
}ST, Stack;

//typedef struct Stack ST;

// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(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 = NULL;
	ps->top = ps->capacity = 0;
}

// 销毁栈
void StackDestroy(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)
	{
		// 空间不够增容
		int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * new_capacity);
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = new_capacity;
	}

	ps->a[ps->top++] = x;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈不能为空
	assert(!StackEmpty(ps));

	--ps->top;
}

// 取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	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;
}

Stack path;	// 路径
/********************************************************/

/* 迷宫问题https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc */

// 示例
/*
输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)


输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

*/


// 打印迷宫
void PrintMaze(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* ps)
{
	// path里面的数据倒入rPath
	Stack rPath;
	StackInit(&rPath);
	while (!StackEmpty(ps))
	{
		StackPush(&rPath, StackTop(ps));
		StackPop(ps);
	}

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

	StackDestroy(&rPath);
}

// 可以通过的位置
bool IsPass(int** maze, int N, int M, PT pos)
{
	if (pos.row >= 0 && pos.row < N
		&& pos.col >= 0 && pos.col < M
		&& maze[pos.row][pos.col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// 路径逻辑函数--N,M行数和列数，cur当前位置
bool GetMazePath(int** maze, int N, int M, PT cur)
{
	StackPush(&path, cur);

	// 如果走到出口
	if (cur.row == N - 1 && cur.col == M - 1)
		return true;

	// 探测cur位置的上下左右四个方向
	PT next;	// 定义下一个位置
	maze[cur.row][cur.col] = 2;	// 走过一个格子就把数置为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, 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);
		}

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

		StackInit(&path);
		// 测试打印迷宫
		//PrintMaze(maze, N, M);

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

		StackDestroy(&path);

		for (int i = 0; i < N; ++i)
		{
			free(maze[i]);	// 先free每一行
		}

		free(maze);	// 再free整个maze
		maze = NULL;
	}

	return 0;
}

2. 迷宫最短路径求解

地下迷宫_滴滴笔试题_牛客网

        本题在曾经是滴滴某一年的笔试题，本题在上一个题的基础上计入了体力值的概念，但是本题还有一个隐藏条件，就是要找出迷宫的最短路径，如下图的两个测试用例，需要找出最短路径，才能通过全部测试用例。

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

// 迷宫坐标结构
typedef struct Position {
	int row;	// 行
	int col;	// 列
}PT;

typedef PT STDataType;

// 栈的结构--建议使用数组
typedef struct Stack {
	STDataType* a;
	int top;	// 栈顶
	int capacity;
}ST, Stack;

//typedef struct Stack ST;

// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(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 = NULL;
	ps->top = ps->capacity = 0;
}

// 销毁栈
void StackDestroy(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)
	{
		// 空间不够增容
		int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * new_capacity);
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = new_capacity;
	}

	ps->a[ps->top++] = x;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈不能为空
	assert(!StackEmpty(ps));

	--ps->top;
}

// 取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	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;
}

Stack path;	// 路径
Stack minpath;	// 最短路径
/********************************************************/

/* 迷宫问题https://www.nowcoder.com/questionTerminal/571cfbe764824f03b5c0bfd2eb0a8ddf */


// 打印迷宫
void PrintMaze(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* ps)
{
	// path里面的数据倒入rPath
	Stack rPath;
	StackInit(&rPath);
	while (!StackEmpty(ps))
	{
		StackPush(&rPath, StackTop(ps));
		StackPop(ps);
	}

	while (StackSize(&rPath) > 1)
	{
		PT top = StackTop(&rPath);
		printf("[%d,%d],", top.row, top.col);
		StackPop(&rPath);
	}

	// 最后一次单独打印
	PT top = StackTop(&rPath);
	printf("[%d,%d]", top.row, top.col);
	StackPop(&rPath);

	StackDestroy(&rPath);
}

// 可以通过的位置
bool IsPass(int** maze, int N, int M, PT pos)
{
	if (pos.row >= 0 && pos.row < N
		&& pos.col >= 0 && pos.col < M
		&& maze[pos.row][pos.col] == 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// 深拷贝
void StackCopy(Stack* ppath, Stack* pcopy)
{
	pcopy->a = (STDataType*)malloc(sizeof(STDataType) * ppath->capacity);
	memcpy(pcopy->a, ppath->a, sizeof(STDataType) * ppath->top);
	pcopy->top = ppath->top;
	pcopy->capacity = ppath->capacity;
}

// 路径逻辑函数--N,M行数和列数，cur当前位置 P体力
void GetMazePath(int** maze, int N, int M, PT cur, int P)
{
	StackPush(&path, cur);

	// 如果走到出口
	if (cur.row == 0 && cur.col == M - 1)
	{
		// 找到了更短的路径，更新minpath
		if (P >= 0 && StackEmpty(&minpath)
			|| StackSize(&path) < StackSize(&minpath))
		{
			StackDestroy(&minpath);
			StackCopy(&path, &minpath);
		}
	}

	// 探测cur位置的上下左右四个方向
	PT next;	// 定义下一个位置
	maze[cur.row][cur.col] = 2;	// 走过一个格子就把数置为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);
	}

	// 恢复一下
	maze[cur.row][cur.col] = 1;
	StackPop(&path);
}

int main()
{
	int N = 0, M = 0, P = 0;
	while (scanf("%d %d %d", &N, &M, &P) != EOF)
	{
		// 动态开辟二维数组
		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]);
			}
		}

		StackInit(&path);
		StackInit(&minpath);
		// 测试打印迷宫
		//PrintMaze(maze, N, M);

		PT entry = { 0, 0 };	// 入口
		GetMazePath(maze, N, M, entry, P);
		
		if (!StackEmpty(&minpath))
		{
			PrintPath(&minpath);
		}
		else
		{
			printf("Can not escape!\n");
		}

		StackDestroy(&path);
		StackDestroy(&minpath);

		for (int i = 0; i < N; ++i)
		{
			free(maze[i]);	// 先free每一行
		}

		free(maze);	// 再free整个maze
		maze = NULL;
	}

	return 0;
}

完


http://www.kler.cn/a/542487.html

相关文章：

  • 【R语言】相关系数
  • 【SVN基础】
  • STM32_USART通用同步/异步收发器
  • MybatisPlus常用增删改查
  • 力扣1448. 统计二叉树中好节点的数目
  • 强化学习之 PPO 算法：原理、实现与案例深度剖析
  • 在nodejs中使用RabbitMQ（三）Routing、Topics、Headers
  • Flink-DataStream API
  • Redis Sentinel（哨兵）模式介绍
  • 力扣动态规划-26【算法学习day.120】
  • DeepSeek API 调用 - Spring Boot 实现
  • 【经验分享】Linux 系统安装后内核参数优化
  • C++中函数的调用
  • 机器学习 - 进一步理解最大似然估计和高斯分布的关系
  • kafka服务端之日志磁盘存储
  • 从零开始设计一个完整的网站：HTML、CSS、PHP、MySQL 和 JavaScript 实战教程
  • 如何评估云原生GenAI应用开发中的安全风险（下）
  • MySQL 中可以通过添加主键来节省磁盘空间吗？（译文）
  • jQuery UI 下载指南
  • 腾讯云HAI部署DeepSeek结合Ollama API搭建智能对话系统
  • [QMT量化交易小白入门]-二十二、deepseek+cline+vscode,让小白使用miniQMT量化交易成为可能
  • MR30分布式IO模块：驱动智能制造工厂的工业互联与高效控制新范式
  • React进行路由跳转的方法汇总
  • 在 Qt 开发中，可以将 QML 封装成库
  • 基于Springmvc+MyBatis+Spring+Bootstrap+EasyUI+Mysql的个人博客系统
  • JVM的栈里面存的是栈帧，栈帧里面存的是什么？