利用栈来破解迷宫问题

利用栈来破解迷宫问题

对于迷宫类问题的破解，需要利用栈的思想
1.构思
假设“当前位置”指的是在搜索过程中某一时刻所在途中某个方块的位置，“路径是最优走法”则求迷宫当中一条路径的思想便是：若当前位置可以通过，那么存放在“路径”中，可以通过的位置便是没有走过的位置，因为路径记录的是每一步，并朝向下一个位置进行探索，切换下一个位置为当前位置。把当前位置用一个数组表示，然后判断放入路径然后用栈存放，那么放进去一个位置就代表走过了那个位置。那肯定有很多重复，也会往回走但，那么如何实现走出迷宫呢？
2.算法
每次走一个位置，就进行判断。如果当前位置可通（可通的概念便是可以走，并且没有走过该位置）那么存入路径中，如果当前位置不可通，那么取出栈中栈顶元素，也就是上一个位置，转一下向，按顺时针（1为右，2为下，3为左，4为上），然后再走，再来判断是否可通，要是四个方向都判断了也就是走完该位置的所有走法了还是没有可以通的位置，那么取出删除，然后再取栈顶，然后继续判断，那么就相当于后退一格到前一个位置，然后继续判断。

假设当前位置的初值为入口位置
do{
    if(当前位置可通）{
    将该位置插入栈顶
    若是出口位置，则走完
    }
    else{
    if（若栈不空并且四周都不通）{
    删除栈顶元素
    }
    if（栈不空并且四周还能走）{
    那么改变方向继续走
    }
    }
}while（栈不空）

代码如下

#include"consts.h"
typedef struct {
	int ord;           //通道块在路径上的序号
	int seat[2];       //通道块在迷宫中的位置
	int di;            //记录此通道块走向下一通道块的方向
}SElemType;
int top = -1;
SElemType Q[100];
int map[10][10] = { 0 };
int foot[200][2] = { 0 };
int l1 = -1;
int badfoot[100][2] = { 0 };
int l2 = -1;


void Push(SElemType* Q, SElemType* e) {
	if (top == 100) {
		printf("栈满");
		exit(0);
	}
	else {
		top++;
		Q[top] = *e;
	}
	int xx, yy;
	for (int i = 0; i <= top; i++) {
		xx = Q[i].seat[0];
		yy = Q[i].seat[1];
	}
}

void Pop(SElemType* Q, SElemType* e) {
	if (top == -1) {
		printf("栈空");
		exit(0);
	}
	else {
		*e = Q[top];
		top--;
	}
}


int StackEmpty(SElemType* Q) {
	if (top == -1)return 1;
	else return 0;
}

int Pass(int curpos[]) {
	int x = curpos[0];
	int y = curpos[1];
	if (map[y][x] == 1)return 0;
	for (int i = 0; i <= top; i++) {
		if (Q[i].seat[0] == x && Q[i].seat[1] == y) {
			return 0;
		}
	}
	return 1;
}

void FootPrint(int curpos[]) {
	l1++;
	foot[l1][0] = curpos[0];
	foot[l1][1] = curpos[1];
}

int* NextPos(int curpos[], int e) {
	if (e == 1) {
		int x = curpos[0] + 1;
		int y = curpos[1];
		int newcur[2];
		newcur[0] = x;
		newcur[1] = y;
		return newcur;
	}
	else if (e == 2) {
		int x = curpos[0];
		int y = curpos[1] + 1;
		int newcur[2];
		newcur[0] = x;
		newcur[1] = y;
		return newcur;
	}
	else if (e == 3) {
		int x = curpos[0] - 1;
		int y = curpos[1];
		int newcur[2];
		newcur[0] = x;
		newcur[1] = y;
		return newcur;
	}
	else if (e == 4) {
		int x = curpos[0];
		int y = curpos[1] - 1;
		int newcur[2];
		newcur[0] = x;
		newcur[1] = y;
		return newcur;
	}
	else return curpos;
}
void MarkPrint(int curpos[]) {
	l2++;
	badfoot[l2][0] = curpos[0];
	badfoot[l2][1] = curpos[1];
}
int main() {
	int win = 0;
	SElemType* S, * e;
	S = (SElemType*)malloc(sizeof(SElemType));
	e = (SElemType*)malloc(sizeof(SElemType));
	if (S) {
		map[1][3] = 1;
		map[1][7] = 1;
		map[2][3] = 1;
		map[2][7] = 1;
		map[3][5] = 1;
		map[3][6] = 1;
		map[4][2] = 1;
		map[4][3] = 1;
		map[4][4] = 1;
		map[5][4] = 1;
		map[6][2] = 1;
		map[6][6] = 1;
		map[7][2] = 1;
		map[7][3] = 1;
		map[7][4] = 1;
		map[7][6] = 1;
		map[7][7] = 1;
		map[8][1] = 1;
		map[1][1] = 2;
		map[8][8] = 3;
		for (int i = 0; i < 10; i++) {
			map[0][i] = 1;
			map[9][i] = 1;
			map[i][0] = 1;
			map[i][9] = 1;
		}
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (map[i][j] == 1)
					printf("*");
				else if (map[i][j] == 2)
					printf("&");
				else if (map[i][j] == 3)
					printf("$");
				else printf(" ");
			}
			printf("\n");
		}
		int curpos[2] = { 1,1 };      //设定当前位置为起始位置
		int curstep = 1;              //探索第一步
		do {
			if (Pass(curpos)) {
				FootPrint(curpos);
				S->seat[0] = curpos[0];
				S->seat[1] = curpos[1];
				S->di = 1;
				S->ord = curstep;
				Push(Q, S);
				int x = curpos[0];
				int y = curpos[1];
				if (map[y][x] == 3) {
					printf("已经出去了\n");
					win = 1;
				}
				int x1 = NextPos(curpos, 1)[0];
				int y1 = NextPos(curpos, 1)[1];
				curpos[0] = x1;
				curpos[1] = y1;
				curstep++;
			}
			else {
				if (!StackEmpty(Q)) {
					Pop(Q, e);
					while (e->di == 4 && !StackEmpty(Q)) {
						MarkPrint(e->seat);
						Pop(Q, e);
					}
					if (e->di < 4) {
						e->di = e->di + 1;
						Push(Q, e);
						int x1 = NextPos(e->seat, e->di)[0];
						int y1 = NextPos(e->seat, e->di)[1];
						curpos[0] = x1;
						curpos[1] = y1;
					}
				}
			}
		} while (!StackEmpty(Q) && win == 0);
		printf("成功破解！\n破解路径:");
		int xx, yy;
		for (int i = 0; i <= top; i++) {
			xx = Q[i].seat[0];
			yy = Q[i].seat[1];
			printf("[%d,%d] ", xx, yy);
		}
		printf("\n破解过程走过的位置:");
		for (int j = 0; j <= l1; j++) {
			printf("[%d,%d]", foot[j][0], foot[j][1]);
		}
	}
}

补充：头文件

#pragma once
#include<stdio.h>                        //EOF(=^Z或F6),NULL
#include<malloc.h>                       //malloc()等
#include<limits.h>                       //INT_MAX等
#include<string.h>                       
#include<stdlib.h>                       //atoi()
#include<io.h>                           //eof
#include<math.h>                         //floor(),ceil(),abs()*
#include<process.h>                      //exit()*
/*函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define INFEASIBLE -1

该算法可以实现大部分迷宫的破解，算法比较简单，如果大佬有更简单的算法，欢迎私聊！

本人在校大学生，菜鸟学习中，欢迎大佬指导，欢迎大家点赞关注！