C++ 迷宫问题求解算法 - 深度优先搜索

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

#define row 8 #define col 11

typedef struct { int x; int y; } Position; // 迷宫坐标结构体

typedef struct { int top; int right; int left; int bottom; } Direction; // 迷宫块的四个方向

typedef struct StackNode { Position position; // 迷宫块的位置 Direction direct; // 迷宫块的四个方向 struct StackNode* next; // 指向下一个迷宫块的指针 } * LinkStackPtr;

typedef struct { LinkStackPtr top; // 栈顶指针 int count; // 栈元素个数 } LinkStack; // 链栈结构体

typedef struct { int x; int y; int seq; } Path; // 探索迷宫的路径结构体

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; // 路径长度

bool Panduan(int x, int y); bool Maze(LinkStack* L); bool IsEmpty(LinkStack *L); void CreateLink(LinkStack *L); LinkStackPtr GetTop(LinkStack *L); void Push(LinkStack *L, LinkStackPtr s); void Pop(LinkStack *L); void RecordExplorationPath(LinkStackPtr m); void PrintPath();

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

while (!IsEmpty(L)) {
	p = GetTop(L);
	int x = p->position.x;
	int y = p->position.y;
	
	// 判断是否到达出口
	if (x == exitx && y == exity) {
		flag = true;
		break;
	}
	
	// 判断上方是否可通行
	if (x > 0 && Panduan(x - 1, y) && p->direct.top == 0) {
		LinkStackPtr s = (LinkStackPtr)malloc(sizeof(struct StackNode));
		s->position.x = x - 1;
		s->position.y = y;
		s->direct.top = 1;
		s->direct.right = 0;
		s->direct.left = 0;
		s->direct.bottom = 0;
		map[s->position.x][s->position.y] = 2;
		Push(L, s);
		RecordExplorationPath(s);
		continue;
	}
	
	// 判断右方是否可通行
	if (y < col - 1 && Panduan(x, y + 1) && p->direct.right == 0) {
		LinkStackPtr s = (LinkStackPtr)malloc(sizeof(struct StackNode));
		s->position.x = x;
		s->position.y = y + 1;
		s->direct.top = 0;
		s->direct.right = 1;
		s->direct.left = 0;
		s->direct.bottom = 0;
		map[s->position.x][s->position.y] = 2;
		Push(L, s);
		RecordExplorationPath(s);
		continue;
	}
	
	// 判断左方是否可通行
	if (y > 0 && Panduan(x, y - 1) && p->direct.left == 0) {
		LinkStackPtr s = (LinkStackPtr)malloc(sizeof(struct StackNode));
		s->position.x = x;
		s->position.y = y - 1;
		s->direct.top = 0;
		s->direct.right = 0;
		s->direct.left = 1;
		s->direct.bottom = 0;
		map[s->position.x][s->position.y] = 2;
		Push(L, s);
		RecordExplorationPath(s);
		continue;
	}
	
	// 判断下方是否可通行
	if (x < row - 1 && Panduan(x + 1, y) && p->direct.bottom == 0) {
		LinkStackPtr s = (LinkStackPtr)malloc(sizeof(struct StackNode));
		s->position.x = x + 1;
		s->position.y = y;
		s->direct.top = 0;
		s->direct.right = 0;
		s->direct.left = 0;
		s->direct.bottom = 1;
		map[s->position.x][s->position.y] = 2;
		Push(L, s);
		RecordExplorationPath(s);
		continue;
	}
	
	// 如果四个方向都无法通行，则出栈
	Pop(L);
}

return flag;

}

// 判断链栈是否为空 bool IsEmpty(LinkStack *L) { if (L->count == 0) 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 = 0; }

// 获取栈顶 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;