第 3 章栈和队列（用递归函数求解迷宫问题(求出所有解)）

1. 背景说明：

若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求出所有合理解并求出最优解

迷宫示意图：

输入文本：

2. 示例代码：

mazeProblem.h

/* 用递归函数求解迷宫问题(求出所有解)头文件 */

#ifndef MAZEPROBLEM_H
#define MAZEPROBLEM_H

#define MAXLENGTH 25			/* 设迷宫最大行列为 25 */

/* 定义墙元素值为 0,可通过路径为 -2, 不能通过路径为 -1 */
typedef int MazeType[MAXLENGTH][MAXLENGTH];

/* 迷宫位置坐标 */
typedef struct {
	int x;
	int y;
} MazePosition;

typedef struct {
	int high;
	int length;
	int minStep;
	int solveNum;
} MazeInfo;

/* 如果存在路径，输出求得的迷宫的解 */
void PrintMazePath(int row, int col, const MazeType* maze);

/* 求出迷宫 maze 中存在从入口 start 到出口 end 的所有可行通道 */
void MazePath(const MazePosition* curPos, const MazePosition* end, MazeInfo* mazeInfo,
	int curStep, MazeType* maze);

#endif

mazeProblem.c

/* 用递归函数求解迷宫问题(求出所有解)源文件 */

#include "mazeProblem.h"
#include <stdio.h>
#include <windows.h>

/* 设置字体颜色，入参为 0 - 15 */
static void SetColor(const unsigned short textColor)
{
	if ((textColor >= 0) && (textColor <= 15)) {
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), textColor);
	} else {
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
	}
}

/* 如果存在路径，输出求得的迷宫的解 */
void PrintMazePath(int row, int col, const MazeType* maze)
{
	for (int i = 0; i < row; ++i) {
		for (int j = 0; j < col; ++j) {
			if ((*maze)[i][j] > 0) {
				SetColor(2);
				printf("%3d", (*maze)[i][j]);
			} else {
				SetColor(7);
				printf("%3d", (*maze)[i][j]);
			}

		}

		printf("\n");
	}
}

/* 求出迷宫 maze 中存在从入口 start 到出口 end 的所有可行通道 */
void MazePath(const MazePosition* curPos, const MazePosition* end, MazeInfo* mazeInfo,
	int curStep, MazeType* maze)
{
	MazePosition nextPos = { 0 };
	/* 上下左右四个方向的行、列增量 */
	MazePosition direc[4] = { { -1, 0 }, { 1 , 0 }, { 0, -1 }, { 0, 1 } };
	for (int i = 0; i <= 3; ++i) {
		nextPos.x = curPos->x + direc[i].x;
		nextPos.y = curPos->y + direc[i].y;
		if ((*maze)[nextPos.x][nextPos.y] == -2) {
			(*maze)[nextPos.x][nextPos.y] = ++curStep;
			if ((nextPos.x != end->x) || (nextPos.y != end->y)) {
				MazePath(&nextPos, end, mazeInfo, curStep, maze);
			} else {
				mazeInfo->minStep = (mazeInfo->minStep > curStep) ? curStep : mazeInfo->minStep;
				++(mazeInfo->solveNum);
				printf("Use %d steps\n\n", curStep);
				PrintMazePath(mazeInfo->high, mazeInfo->length, maze);
				printf("\n\n");
			}

			(*maze)[nextPos.x][nextPos.y] = -2;
			--curStep;
		}
	}
}

main.c

/* 入口程序源文件 */

#include "mazeProblem.h"
#include <stdio.h>
#include <limits.h>

int main(void)
{
	printf("Please input the row and col of the maze: ");
	int row = 0, col = 0;
	scanf_s("%d%d", &row, &col);
	MazeInfo mazeInfo = { row, col, INT_MAX, 0 };
	MazeType maze = { 0 };
	for (int i = 0; i < col; ++i) {
		maze[0][i] = 0;
		maze[row - 1][i] = 0;
	}

	for (int i = 1; i < row - 1; ++i) {
		maze[i][0] = 0;
		maze[i][row - 1] = 0;
	}

	for (int i = 1; i < row - 1; ++i) {
		for (int j = 1; j < col - 1; ++j) {
			maze[i][j] = -2;
		}
	}

	printf("Please input the num of the wall: ");
	int wallNum = 0;
	scanf_s("%d", &wallNum);
	printf("Please input the position of the wall(x, y): \n");
	int x = 0, y = 0;
	for (int i = 0; i < wallNum; ++i) {
		scanf_s("%d%d", &x, &y);
		maze[x][y] = 0;
	}

	printf("The structure of the maze is:\n");
	PrintMazePath(row, col, &maze);
	MazePosition start = { 0 }, end = { 0 };
	printf("Please input the position of the start point(x, y):");
	scanf_s("%d%d", &start.x, &start.y);
	maze[start.x][start.y] = 1;
	printf("Please input the position of the end point(x, y):");
	scanf_s("%d%d", &end.x, &end.y);
	MazePath(&start, &end, &mazeInfo, 1, &maze);
	printf("Min Steps: %d\n", mazeInfo.minStep);
	printf("Total solves: %d\n", mazeInfo.solveNum);

	return 0;
}

3. 输出示例：