C语言迷宫求解算法：深度优先搜索实现

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

#define row 8 #define col 11

#include 'maze.h'

int map[row][col] = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1}, {1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1}, {1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} }; // 迷宫地图，1代表墙壁，0代表路

int enterx = 1, entery = 1; // 入口坐标 int exitx = 6, exity = 9; // 出口坐标

Path path[(row - 1) * (col - 1)]; // 探索迷宫的路径 int pathLength = 0; // 路径长度

int main(int argc, char* argv[]) { LinkStack L; L.count = 0; CreateLink(&L);

bool flag = Maze(&L);
	
if (flag == true) {
	PrintPath();
} else {
	printf('Can not find path');
}

return 0;

}

// 判断是否是走过的迷宫块 bool Panduan(int x, int y) { if (map[x][y] == 0) { return true; }

return false;

}

// 探索迷宫可通行的路径 bool Maze(LinkStack* L) { bool flag = false;

LinkStackPtr p;
p = (LinkStackPtr)malloc(sizeof(struct StackNode));
p->position.x = enterx;
p->position.y = entery;
p->direct.top = 1;
p->direct.right = 0;
p->direct.left = 0;
p->direct.bottom = 0;
map[p->position.x][p->position.y] = 2;

// 将入口结点入栈
Push(L, p);

//
//	TODO: 实现迷宫算法
//
while (!IsEmpty(L)) {
	p = GetTop(L);
	if (p->position.x == exitx && p->position.y == exity) {
		flag = true;
		break;
	}
	if (p->direct.top && Panduan(p->position.x - 1, p->position.y)) {
		p->direct.top = 0;
		LinkStackPtr q = (LinkStackPtr)malloc(sizeof(struct StackNode));
		q->position.x = p->position.x - 1;
		q->position.y = p->position.y;
		q->direct.top = 1;
		q->direct.right = 0;
		q->direct.left = 0;
		q->direct.bottom = 0;
		map[q->position.x][q->position.y] = 2;
		RecordExplorationPath(q);
		Push(L, q);
	} else if (p->direct.right && Panduan(p->position.x, p->position.y + 1)) {
		p->direct.right = 0;
		LinkStackPtr q = (LinkStackPtr)malloc(sizeof(struct StackNode));
		q->position.x = p->position.x;
		q->position.y = p->position.y + 1;
		q->direct.top = 0;
		q->direct.right = 1;
		q->direct.left = 0;
		q->direct.bottom = 0;
		map[q->position.x][q->position.y] = 2;
		RecordExplorationPath(q);
		Push(L, q);
	} else if (p->direct.bottom && Panduan(p->position.x + 1, p->position.y)) {
		p->direct.bottom = 0;
		LinkStackPtr q = (LinkStackPtr)malloc(sizeof(struct StackNode));
		q->position.x = p->position.x + 1;
		q->position.y = p->position.y;
		q->direct.top = 0;
		q->direct.right = 0;
		q->direct.left = 0;
		q->direct.bottom = 1;
		map[q->position.x][q->position.y] = 2;
		RecordExplorationPath(q);
		Push(L, q);
	} else if (p->direct.left && Panduan(p->position.x, p->position.y - 1)) {
		p->direct.left = 0;
		LinkStackPtr q = (LinkStackPtr)malloc(sizeof(struct StackNode));
		q->position.x = p->position.x;
		q->position.y = p->position.y - 1;
		q->direct.top = 0;
		q->direct.right = 0;
		q->direct.left = 1;
		q->direct.bottom = 0;
		map[q->position.x][q->position.y] = 2;
		RecordExplorationPath(q);
		Push(L, q);
	} else {
		Pop(L);
	}
}

return flag;

}

// 判断链栈是否为空 bool IsEmpty(LinkStack *L) { if (L->count == 1) return true; return false; }

// 创建链栈 void CreateLink(LinkStack *L) { L->top = (LinkStackPtr)malloc(sizeof(struct StackNode)); if (!L->top) { exit(1); } L->top = NULL; L->count++; }

// 获取栈顶 LinkStackPtr GetTop(LinkStack *L) { return L->top; }

// 进栈 void Push(LinkStack *L, LinkStackPtr s) { s->next = L->top; L->top = s; L->count++; }

// 出栈 void Pop(LinkStack *L) { LinkStackPtr p; if (IsEmpty(L)) { return; } p = L->top; L->top = L->top->next; free(p); L->count--; }

// 记录探索路径 void RecordExplorationPath(LinkStackPtr m){ path[pathLength].x = m->position.x; path[pathLength].y = m->position.y; path[pathLength].seq = pathLength + 1; pathLength += 1; }

// 打印迷宫可通行的路径 void PrintPath(){ for (int i = 0; i < pathLength; i++) { printf('%d:(%d, %d)\n',path[i].seq, path[i].x, path[i].y); } return; }

/* 这是一个迷宫问题，请严格根据注释，补全代码，不能有任何错误！内容：这个代码是一个求解迷宫路径的程序。主要思路是使用深度优先搜索算法来探索迷宫。代码中使用了一个链栈来记录探索的路径。

在代码中，首先定义了迷宫地图的二维数组map，其中1表示墙壁，0表示通路。然后定义了入口坐标(enterx, entery)和出口坐标(exitx, exity)。

接下来定义了一个结构体Path来记录路径信息，以及一个全局变量path来存储路径数组，pathLength表示路径的长度。

在main函数中，创建了一个链栈L，然后调用Maze函数进行迷宫的探索。如果找到了路径，则打印路径；否则，打印'Can not find path'。

在Maze函数中，首先创建了一个结点p，初始化其位置为入口坐标，并将其入栈。然后使用循环进行迷宫的探索，直到栈为空或者找到了出口。在每一步探索中，先判断当前位置是否是可以走的路径，如果是，则将其入栈，并将其设置为已走过的块，然后记录探索路径。如果当前位置是出口，设置标志位flag为true，并结束探索。如果当前位置没有可走的路径，则将其出栈。

在Panduan函数中，判断给定的坐标是否是已走过的路径。如果是，则返回true；否则，返回false。

在IsEmpty函数中，判断链栈是否为空。如果链栈中只有一个结点，返回true；否则，返回false。

在CreateLink函数中，创建一个链栈，并将栈顶指针初始化为NULL。

在GetTop函数中，获取链栈的栈顶指针。

在Push函数中，将一个结点入栈。

在Pop函数中，将栈顶的结点出栈。

在RecordExplorationPath函数中，记录探索的路径。

在PrintPath函数中，打印路径。

请根据注释，完善代码中的TODO部分，实现迷宫算法。