• ＜迷宫问题及最短路径问题（使用DFS与回溯法求解）＞——《算法》

    目录

    一、迷宫问题： 

    1.迷宫问题链接：（牛客网）迷宫问题

    1.1 问题描述：

    1.2 问题分析：

    1.3 功能函数实现：

    1.4 栈的模拟实现：

    1.5测试用例及演示：

    1.6 完整源码：

    二、迷宫最短路径问题： 

    1. 迷宫最短路径问题链接：（牛客网）地下迷宫

    1.1 问题描述：

    1.2 问题分析：

    1.3 功能函数实现：

    1.4 栈的模拟实现：

    1.5测试用例及演示：

    1.6 完整源码：

    三、总结：

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

    一、迷宫问题： 

    1.迷宫问题链接：（牛客网）迷宫问题

    1.1 问题描述：

     

    1.2 问题分析：

    以上迷宫OJ题曾经是百度某一年的其中一个笔试题，迷宫问题本质就是一个图的遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标，栈记录坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路。这里涉及到四路递归。（上、下、左、右四个方向的递归）
    我们在这里借助深度优先遍历（DFS）与回溯法进行分析、求解。
    根据题目要求，分析后确定实现方式，模块化实现各部分功能，然后依据“高内聚，低耦合”的方式进行组织！

     

    1.3 功能函数实现：

    （1）首先定义迷宫坐标位置的结构体：

     

    （2）写出调用逻辑（主函数）：

     

     

    （3）判断路径坐标进行可以进行遍历：

     

     

    （4）判断该坐标是否为有效可遍历的坐标

     （5） 输出栈里面的坐标路径：

    由于栈的“FIFO”性质，又题目要求按照从最开始打印，则需要进行顺序调整。

     （6）打印遍历的路径坐标：

     1.4 栈的模拟实现：

    （这里借助栈的“FIFO”性质，借用栈存储递归遍历的数据存储，不符合的坐标就出栈，再进行回溯遍历）

     1.5测试用例及演示：

    示例1：

    1. 5 5
    2. 0 1 0 0 0
    3. 0 1 1 1 0
    4. 0 0 0 0 0
    5. 0 1 1 1 0
    6. 0 0 0 1 0

    示例2：

    1. 5 5
    2. 0 1 0 0 0
    3. 0 1 0 1 0
    4. 0 0 0 0 1
    5. 0 1 1 1 0
    6. 0 0 0 0 0

     测试打印：

     1.6 完整源码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. //定义位置结构体
    7. typedef struct Postion
    8. {
    9. 	int row;
    10. 	int col;
    11. }PT;
    12. /
    13. //栈的实现
    14. typedef PT STDataType;
    15.  
    16. typedef struct Stack
    17. {
    18. 	STDataType* a;   //通过数组实现栈的结构
    19. 	int top;
    20. 	int capacity;
    21. }ST;
    22. //初始化
    23. void StackInit(ST* ps);
    24. //释放内存、销毁空间
    25. void StackDestory(ST* ps);
    26. // 入栈
    27. void StackPush(ST* ps, STDataType x);
    28. // 出栈
    29. void StackPop(ST* ps);
    30. //取栈顶数据
    31. STDataType StackTop(ST* ps);
    32. //栈的大小
    33. int StackSize(ST* ps);
    34. //判空
    35. bool StackEmpty(ST* ps);
    36. //初始化
    37. void StackInit(ST* ps)
    38. {
    39. 	assert(ps);
    40.  
    41. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    42. 	if (ps->a == NULL)
    43. 	{
    44. 		printf("malloc fail!\n");
    45. 		exit(-1);
    46. 	}
    47.  
    48. 	ps->capacity = 4;
    49. 	ps->top = 0; //这使得top最终指向的是栈顶的后一个位置。若top=-1,则最终指向的是栈顶。
    50. }
    51. //释放内存、销毁空间
    52. void StackDestory(ST* ps)
    53. {
    54. 	assert(ps);
    55. 	free(ps->a);
    56. 	ps->a = NULL;
    57. 	ps->top = ps->capacity = 0;
    58. }
    59. // 入栈
    60. void StackPush(ST* ps, STDataType x)
    61. {
    62. 	assert(ps);
    63.  
    64. 	// 满了->增容
    65. 	if (ps->top == ps->capacity)
    66. 	{
    67. 		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
    68. 		if (tmp == NULL)
    69. 		{
    70. 			printf("realloc fail!\n");
    71. 			exit(-1);
    72. 		}
    73. 		else
    74. 		{
    75. 			ps->a = tmp;
    76. 			ps->capacity *= 2;
    77. 		}
    78. 	}
    79.  
    80. 	ps->a[ps->top] = x;
    81. 	ps->top++;
    82. }
    83.  
    84. // 出栈
    85. void StackPop(ST* ps)
    86. {
    87. 	assert(ps);
    88. 	// 栈空了，再调用Pop，就会直接中止程序报错
    89. 	assert(ps->top > 0);
    90.  
    91. 	//ps->a[ps->top - 1] = 0; //置为0只考虑了int型等，若为char、double等就不适用了。
    92. 	ps->top--;
    93. }
    94. //取栈顶数据
    95. STDataType StackTop(ST* ps)
    96. {
    97. 	assert(ps);
    98. 	// 栈空了，再调用Top，就会直接中止程序报错
    99. 	assert(ps->top > 0);
    100.  
    101. 	return ps->a[ps->top - 1];
    102. }
    103. //求栈大小
    104. int StackSize(ST* ps)
    105. {
    106. 	assert(ps);
    107.  
    108. 	return ps->top;
    109. }
    110. //判空
    111. bool StackEmpty(ST* ps)
    112. {
    113. 	assert(ps);
    114. 	return ps->top == 0;
    115. }
    116.  
    117. //maze实现
    118. ST path;  //定义全局变量
    119. //打印
    120. void PrintMaze(int** maze, int N, int M)
    121. {
    122. 	for (int i = 0; i < N; ++i)
    123. 	{
    124. 		for (int j = 0; j < M; ++j)
    125. 		{
    126. 			printf("%d ", maze[i][j]);
    127. 		}
    128. 		printf("\n");
    129. 	}
    130. 	printf("\n");
    131. }
    132.  
    133. // 输出栈里面的坐标路径
    134. //要求从最开始的坐标先输出，而栈是后进先出，需要调整输出
    135. void PirntPath(ST* ps)
    136. {
    137. 	// path数据倒到rPath
    138. 	ST rPath;
    139. 	StackInit(&rPath);
    140. 	while (!StackEmpty(&path))
    141. 	{
    142. 		StackPush(&rPath, StackTop(&path));
    143. 		StackPop(&path);
    144. 	}
    145.  
    146. 	while (!StackEmpty(&rPath))
    147. 	{
    148. 		PT top = StackTop(&rPath);
    149. 		printf("(%d,%d)\n", top.row, top.col);
    150. 		StackPop(&rPath);
    151. 	}
    152.  
    153. 	StackDestory(&rPath);
    154. }
    155. //判断该坐标是否为有效可遍历的坐标
    156. bool IsPass(int** maze, int N, int M, PT pos)
    157. {
    158. 	if (pos.row >= 0 && pos.row < N
    159. 		&& pos.col >= 0 && pos.col < M
    160. 		&& maze[pos.row][pos.col] == 0)
    161. 	{
    162. 		return true;
    163. 	}
    164. 	else
    165. 	{
    166. 		return false;
    167. 	}
    168. }
    169. //判断路径坐标进行可以进行遍历
    170. bool GetMazePath(int** maze, int N, int M, PT cur)
    171. {
    172. 	StackPush(&path, cur);
    173.  
    174. 	// 如果走到出口
    175. 	if (cur.row == N - 1 && cur.col == M - 1)
    176. 		return true;
    177.  
    178. 	// 探测cur位置得上、下、左、右四个方向
    179. 	PT next;
    180. 	maze[cur.row][cur.col] = 2;  //已经遍历过的（包括当前）位置，标记为2
    181.  
    182. 	//向上遍历
    183. 	next = cur;
    184. 	next.row -= 1;
    185. 	if (IsPass(maze, N, M, next))
    186. 	{
    187. 		if (GetMazePath(maze, N, M, next))
    188. 			return true;
    189. 	}
    190.  
    191. 	//向下遍历 
    192. 	next = cur;
    193. 	next.row += 1;
    194. 	if (IsPass(maze, N, M, next))
    195. 	{
    196. 		if (GetMazePath(maze, N, M, next))
    197. 			return true;
    198. 	}
    199.  
    200. 	//向左遍历
    201. 	next = cur;
    202. 	next.col -= 1;
    203. 	if (IsPass(maze, N, M, next))
    204. 	{
    205. 		if (GetMazePath(maze, N, M, next))
    206. 			return true;
    207. 	}
    208.  
    209. 	//向右遍历
    210. 	next = cur;
    211. 	next.col += 1;
    212. 	if (IsPass(maze, N, M, next))
    213. 	{
    214. 		if (GetMazePath(maze, N, M, next))
    215. 			return true;
    216. 	}
    217.  
    218. 	StackPop(&path);  //不通，这个坐标不能使用，就出栈
    219.  
    220. 	return false; //四个方向都不通，就返回false,递归会回溯，探索其他通路
    221. }
    222.  
    223. int main()
    224. {
    225. 	int N = 0, M = 0;
    226. 	while (scanf("%d%d", &N, &M) != EOF)
    227. 	{
    228. 		// int a[n][m]; // vs2013 不支持
    229. 		// 动态开辟二维数组
    230. 		int** maze = (int**)malloc(sizeof(int*) * N);
    231. 		for (int i = 0; i < N; ++i)
    232. 		{
    233. 			maze[i] = (int*)malloc(sizeof(int) * M);
    234. 		}
    235.  
    236. 		// 二维数组的输入
    237. 		for (int i = 0; i < N; ++i)
    238. 		{
    239. 			for (int j = 0; j < M; ++j)
    240. 			{
    241. 				scanf("%d", &maze[i][j]);
    242. 			}
    243. 		}
    244.  
    245. 		StackInit(&path);
    246. 		// PrintMaze(maze, N, M);
    247. 		PT entry = { 0, 0 };       //入口
    248. 		if (GetMazePath(maze, N, M, entry))
    249. 		{
    250. 			//printf("找到通路\n");
    251. 			PirntPath(&path);
    252. 		}
    253. 		else
    254. 		{
    255. 			printf("没有找到通路\n");
    256. 		}
    257.  
    258. 		StackDestory(&path);
    259.  
    260. 		for (int i = 0; i < N; ++i)
    261. 		{
    262. 			free(maze[i]);
    263. 		}
    264. 		free(maze);
    265. 		maze = NULL;
    266. 	}
    267.  
    268. 	return 0;
    269. }

    二、迷宫最短路径问题： 

    1. 迷宫最短路径问题链接：（牛客网）地下迷宫

    1.1 问题描述：

     1.2 问题分析：

    本题在曾经是美团某一年的笔试题，本题在上一个题的基础上计入了体力值的概念，但是本题还有一个隐藏条件，就是要找出迷宫的最短路径，如下图的两个测试用例，需要找出最短路径，才能通过全部测试用例。本题依旧借助深度优先遍历（DFS）和回溯法解决。这里涉及到四路递归，（上、下、左、右四个方向的递归）。
    分析问题，确定求解方法：
    根据题目可知：相比于“迷宫问题”，这题在上题的基础上进行了“变种”，即引入了“体力值”和最短路径，而且路径也从“只有一条”变为了“多条路径”，因此，要进行分析，将各个功能模块封装后，依据“高内聚，低耦合”的设计原则进行组织。

    1.3 功能函数实现：

    （1）定义迷宫坐标的结构体：

    （2）写出调用逻辑（主函数）：

    （3）获取有效遍历的有效路径坐标： 

    （4）解决浅拷贝的两次释放空间会报错问题：

     

    （5）判断该坐标是否为有效可遍历的坐标：

     

    （6）输出栈里存储的路径坐标：

    由于栈的“FIFO”性质，又题目要求按照从最开始打印，则需要进行顺序调整。

     

    （7）打印遍历的有效路径坐标：

     

     1.4 栈的模拟实现：

    （这里借助栈的“FIFO”性质，借用栈存储递归遍历的数据存储，不符合的坐标就出栈，再进行回溯遍历）

     1.5测试用例及演示：

    示例1：

    1.6 完整源码：

    1. //2.迷宫最短路径问题
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. //定义迷宫坐标的结构体
    8. typedef struct Postion
    9. {
    10. 	int row;
    11. 	int col;
    12. }PT;
    13. /
    14. //栈的实现
    15. typedef PT STDataType;
    16.  
    17. typedef struct Stack
    18. {
    19. 	STDataType* a;   //通过数组实现栈的结构
    20. 	int top;
    21. 	int capacity;
    22. }ST;
    23. //初始化
    24. void StackInit(ST* ps);
    25. //释放内存、销毁空间
    26. void StackDestory(ST* ps);
    27. // 入栈
    28. void StackPush(ST* ps, STDataType x);
    29. // 出栈
    30. void StackPop(ST* ps);
    31. //取栈顶数据
    32. STDataType StackTop(ST* ps);
    33. //栈的大小
    34. int StackSize(ST* ps);
    35. //判空
    36. bool StackEmpty(ST* ps);
    37. //初始化
    38. void StackInit(ST* ps)
    39. {
    40. 	assert(ps);
    41.  
    42. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    43. 	if (ps->a == NULL)
    44. 	{
    45. 		printf("malloc fail!\n");
    46. 		exit(-1);
    47. 	}
    48.  
    49. 	ps->capacity = 4;
    50. 	ps->top = 0; //这使得top最终指向的是栈顶的后一个位置。若top=-1,则最终指向的是栈顶。
    51. }
    52. //释放内存、销毁空间
    53. void StackDestory(ST* ps)
    54. {
    55. 	assert(ps);
    56. 	free(ps->a);
    57. 	ps->a = NULL;
    58. 	ps->top = ps->capacity = 0;
    59. }
    60. // 入栈
    61. void StackPush(ST* ps, STDataType x)
    62. {
    63. 	assert(ps);
    64.  
    65. 	// 满了->增容
    66. 	if (ps->top == ps->capacity)
    67. 	{
    68. 		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
    69. 		if (tmp == NULL)
    70. 		{
    71. 			printf("realloc fail!\n");
    72. 			exit(-1);
    73. 		}
    74. 		else
    75. 		{
    76. 			ps->a = tmp;
    77. 			ps->capacity *= 2;
    78. 		}
    79. 	}
    80.  
    81. 	ps->a[ps->top] = x;
    82. 	ps->top++;
    83. }
    84.  
    85. // 出栈
    86. void StackPop(ST* ps)
    87. {
    88. 	assert(ps);
    89. 	// 栈空了，再调用Pop，就会直接中止程序报错
    90. 	assert(ps->top > 0);
    91.  
    92. 	//ps->a[ps->top - 1] = 0; //置为0只考虑了int型等，若为char、double等就不适用了。
    93. 	ps->top--;
    94. }
    95. //取栈顶数据
    96. STDataType StackTop(ST* ps)
    97. {
    98. 	assert(ps);
    99. 	// 栈空了，再调用Top，就会直接中止程序报错
    100. 	assert(ps->top > 0);
    101.  
    102. 	return ps->a[ps->top - 1];
    103. }
    104. //求栈大小
    105. int StackSize(ST* ps)
    106. {
    107. 	assert(ps);
    108.  
    109. 	return ps->top;
    110. }
    111. //判空
    112. bool StackEmpty(ST* ps)
    113. {
    114. 	assert(ps);
    115. 	return ps->top == 0;
    116. }
    117.  
    118. //maze实现
    119. ST path;  //定义全局变量
    120. ST minpath;  //定义最短路径
    121. //打印
    122. void PrintMaze(int** maze, int N, int M)
    123. {
    124. 	for (int i = 0; i < N; ++i)
    125. 	{
    126. 		for (int j = 0; j < M; ++j)
    127. 		{
    128. 			printf("%d ", maze[i][j]);
    129. 		}
    130. 		printf("\n");
    131. 	}
    132. 	printf("\n");
    133. }
    134.  
    135. // 输出栈里面的坐标路径
    136. //要求从最开始的坐标先输出，而栈是后进先出，需要调整输出
    137. void PirntPath(ST* ps)
    138. {
    139. 	// path数据倒到rPath
    140. 	ST rPath;
    141. 	StackInit(&rPath);
    142. 	while (!StackEmpty(ps))
    143. 	{
    144. 		StackPush(&rPath, StackTop(ps));
    145. 		StackPop(ps);
    146. 	}
    147. 	//输出分为两种，仅因为题目要求，这里没有什么特定含义
    148. 	while (StackSize(&rPath)>1)
    149. 	{
    150. 		PT top = StackTop(&rPath);
    151. 		printf("[%d,%d],", top.row, top.col);
    152. 		StackPop(&rPath);
    153. 	}
    154. 	PT top = StackTop(&rPath);
    155. 	printf("[%d,%d]", top.row, top.col);
    156. 	StackPop(&rPath);
    157. 	StackDestory(&rPath);
    158. }
    159. //判断该坐标是否为有效可遍历的坐标
    160. bool IsPass(int** maze, int N, int M, PT pos)
    161. {
    162. 	if (pos.row >= 0 && pos.row < N
    163. 		&& pos.col >= 0 && pos.col < M
    164. 		&& maze[pos.row][pos.col] == 1)
    165. 	{
    166. 		return true;
    167. 	}
    168. 	else
    169. 	{
    170. 		return false;
    171. 	}
    172. }
    173. //解决浅拷贝的两次释放空间报错问题
    174. void StackCopy(ST* ppath, ST* pcopy)
    175. {
    176. 	pcopy->a = (STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);
    177. 	memcpy(pcopy->a, ppath->a, sizeof(STDataType) * ppath->top);
    178. 	pcopy->top = ppath->top;
    179. 	pcopy->capacity = ppath->capacity;
    180. }
    181. //获取可有效遍历的路径坐标
    182. void GetMazePath(int** maze, int N, int M, PT cur,int P)
    183. {
    184. 	StackPush(&path, cur);
    185. 	// 如果走到出口
    186. 	if (cur.row == 0 && cur.col == M - 1)
    187. 	{
    188. 		// 找到了更短的路径，更新minpath；  //P是题目要求的体力值，要求在有效范围内
    189. 		if (P >= 0 && StackEmpty(&minpath) 
    190. 			|| StackSize(&path) < StackSize(&minpath))
    191. 		{
    192. 			StackDestory(&minpath);
    193. 			StackCopy(&path, &minpath);
    194. 		}
    195. 	}
    196.  
    197. 	// 探测cur位置得上下左右四个方向
    198. 	PT next;
    199. 	maze[cur.row][cur.col] = 2;  //已经走过得，标记为2
    200.  
    201. 	//向上遍历
    202. 	next = cur;
    203. 	next.row -= 1;
    204. 	if (IsPass(maze, N, M, next))
    205. 	{
    206. 		 (GetMazePath(maze, N, M, next, P - 3));
    207. 			
    208. 	}
    209.  
    210. 	//向下遍历
    211. 	next = cur;
    212. 	next.row += 1;
    213. 	if (IsPass(maze, N, M, next))
    214. 	{
    215. 		 (GetMazePath(maze, N, M, next, P));
    216. 			
    217. 	}
    218.  
    219. 	//向左遍历
    220. 	next = cur;
    221. 	next.col -= 1;
    222. 	if (IsPass(maze, N, M, next))
    223. 	{
    224. 		(GetMazePath(maze, N, M, next, P - 1));
    225. 			
    226. 	}
    227.  
    228. 	//向右遍历
    229. 	next = cur;
    230. 	next.col += 1;
    231. 	if (IsPass(maze, N, M, next))
    232. 	{
    233. 		(GetMazePath(maze, N, M, next, P - 1));
    234. 			
    235. 	}
    236.  
    237. 	//递归会回溯，探索其他通路
    238. 	//需要恢复
    239. 	maze[cur.row][cur.col] = 1;
    240. 	StackPop(&path);
    241. }
    242.  
    243. int main()
    244. {
    245. 	int N = 0, M = 0, P = 0;
    246. 	while (scanf("%d%d%d", &N, &M,&P) != EOF)
    247. 	{
    248. 		//创建迷宫，获取迷宫地图
    249. 		// int a[n][m]; // vs2013 不支持
    250. 		// 动态开辟二维数组
    251. 		int** maze = (int**)malloc(sizeof(int*) * N);
    252. 		for (int i = 0; i < N; ++i)
    253. 		{
    254. 			maze[i] = (int*)malloc(sizeof(int) * M);
    255. 		}
    256.  
    257. 		// 二维数组的输入
    258. 		for (int i = 0; i < N; ++i)
    259. 		{
    260. 			for (int j = 0; j < M; ++j)
    261. 			{
    262. 				scanf("%d", &maze[i][j]);
    263. 			}
    264. 		}
    265.  
    266. 		StackInit(&path);
    267. 		StackInit(&minpath);
    268.  
    269. 		// PrintMaze(maze, N, M);
    270. 		PT entry = { 0, 0 };        // 默认[0,0]是入口，[N-1][M-1]是出口
    271. 		GetMazePath(maze, N, M, entry, P);  //获取遍历到的有效路径
    272. 		if (!StackEmpty(&minpath))
    273. 		{
    274. 			PirntPath(&minpath);
    275. 		}
    276. 		else
    277. 		{
    278. 			printf("Can not escape!\n");
    279. 		}
    280. 		
    281. 		StackDestory(&path);
    282. 		StackDestory(&minpath);
    283. 		//销毁迷宫
    284. 		for (int i = 0; i < N; ++i)
    285. 		{
    286. 			free(maze[i]);
    287. 		}
    288. 		free(maze);
    289. 		maze = NULL;
    290. 	}
    291.  
    292. 	return 0;
    293. }

    三、总结：

     通过迷宫问题及最短路径问题，借助深度优先遍历（DFS）和回溯法求解，这里涉及到四路递归（上、下、左、右四个方向的递归），然而解决方法是一方面，解决工具也是另一方面。这里采用C语言实现求解，借助数据结构中栈的性质，实现深度遍历过程中的数据存储，然后回溯。使用C语言，涉及到二维数组的操作，这里使用了二级指针和指针数组，而在最短路径的比较更新中，涉及到了深浅拷贝问题，这里也需要注意，否则程序将会崩溃！

    解决这些题的方法还有很多，解决的工具也有很多，这里不再一一列举！

    最后，向前人的智慧结晶致敬！学者，亦有敬畏之心！亦当珍惜学习的机会与时光！

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

  • 相关阅读:
    关于面试，95%会问到的Java面试题（高级部分）
    SSH安全外壳协议
    mp4视频太大怎么压缩变小？
    【嵌入式开源库】EasyLogger的使用, 一款轻量级且高性能的日志库
    用于构建用户界面的JavaScript库---＞React
    三台linux服务器部署ceph集群
    皕杰报表之调整css样式
    擎创技术流 | ckman教程（3）CKman源码分析部署集群的主要步骤
    为什么数据集中的mask是彩色的？
    安装GPT 学术优化 (GPT Academic)@FreeBSD
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126665880