首页 » 技术分享 » (十三)栈的应用 --- 迷宫解题五行八卦阵

(十三)栈的应用 --- 迷宫解题五行八卦阵

 

迷宫解题

迷宫解题是我最喜欢的栈的实际应用,可以用来做一些外挂,具体什么外挂?呵呵。。自己好好想想。
在这里插入图片描述
这个迷宫能走出来吗?我想99.999%的人都能够解出来。用笔沿着空白处画,路不通折回去再走下一条路,直到出口处。这里我们用的是穷举法,但是如何让计算机按照我们的思维进行路径选择呢?这就可以用到我们的栈结构了。栈能够依次保留你所经过的路径,并能够遇到死胡同后按照原路返回。
下边就说一下思路

  • 如何判定方向? 从入口位置按照固定的方向行走,比如约定第一步向左,如果不通,则向下,不通再向右,不通最后向上。这样就可以定义4个数值分别为1、2、3、4,分别代表左、下、右、上。这个顺序你自己可以定义,只要在程序中按照你规定的方向实现就行。
  • 怎么判断遇到障碍物或者已经走过的线路? 这个问题就是核心问题了。我用一个二维数组来模拟迷宫,约定数字1位障碍物,数字0位道路,数字2位已经通过的路径,数字3表示已经无路可走的路径。
  • 栈在迷宫解题中怎么应用? 这个问题是不少初学者疑惑的,简单的栈会用,但是灵活一点就不知道该如何使用了。压栈是将可以通过的路径的信息保存到栈中。那什么时候弹栈呢?就是遇到障碍物或者已经走过的路径。
  • 怎么判断是死胡同呢? 这个就是很巧妙的运用到栈元素结构中的方向字段,如果4个方向都不能通行,则判定为死路一条。将栈顶元素弹出来,改变个方向,再压入,循环到4个方向都不通时,倒着将坐标对应数值改为3,并且弹栈。如果弹出的元素方向信息不为4,则接着找,否则接着弹栈。

下边通过实际代码详细讲一下。

  1. 数据机构的变化
    为了能够符合解题思路,需要创建一个新的结构,而且这个结构中应当包含位置、方向、步骤信息。将原来sqstack.h中的SElemType 定义修改成下边的代码。
typedef struct
{
	int x;  //坐标x
	int y;  //坐标y
} PosType;
typedef  struct
{
	int ord; //步骤
	PosType seat;  //坐标信息
	int di;   //方向
} SElemType;
  1. 模拟迷宫
    如何让计算机知道哪些是障碍物,哪些能够通过,我这里用一个二维数组进行模拟。
void Init_Maze(int* s)
{
	int i,j;
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 10; j++)
		{
			*(s + i * 10 + j) = 0;
		}
	}
	for (i = 0; i < 10; i++)
	{
		*(s + i) = 1;  //第一行
		*(s + 9 * 10 + i) = 1;//第10行
		*(s + i * 10) = 1; //第一列
		*(s + i * 10 + 9) = 1; //最后一列
	}
	//其他零星数据块
	*(s + 10 + 3) = 1;	*(s + 10 + 7) = 1;
	*(s + 20 + 3) = 1;	*(s + 20 + 7) = 1;	
	*(s + 30 + 5) = 1;	*(s + 30 + 6) = 1;
	*(s + 40 + 2) = 1;	*(s + 40 + 3) = 1;	*(s + 40 + 4) = 1;
	*(s + 50 + 4) = 1;	
	*(s + 60 + 2) = 1;	*(s + 60 + 6) = 1;
	*(s + 70 + 2) = 1;	*(s + 70 + 3) = 1;	*(s + 70 + 4) = 1;	*(s + 70 + 6) = 1;	*(s + 70 + 7) = 1;	
	*(s + 80 + 1) = 1;
	Print_Maze(s);
}

效果是什么呢?
在这里插入图片描述
怎么样,和上边的迷宫差不多一致。看看求出的路径是怎么样的。
在这里插入图片描述
数字2代表着线路,数字3则代表的是死胡同。我把步骤也打印出来。
在这里插入图片描述

  1. 核心代码
    通过穷举法视图将说有的路径找到,知道找到出口为止。
Status MazePath()
{
	/*
	迷宫类型:1 为墙体
			  0 为未到过
			  2 为已经到
			  3 为此路不通
	*/
	int maze[10][10];
	SqStack sstack;
	PosType start, end,curpos;
	int user_step = 0;
	SElemType cur_e;
	SElemType* le=NULL;
	SElemType* ll = NULL;
	int n=0;

	printf("初始化迷宫:\n");
	Init_Maze(maze);
	Init_Stack(&sstack);
	//起始坐标
	start.x = 1;
	start.y = 1;
	//出口坐标
	end.x = 8;
	end.y = 8;

	curpos.x = start.x; 
	curpos.y = start.y;
	user_step = 1;
	do
	{
		if (Pass(maze, &curpos)) //判断此节点是否到过,如果对应数组中为0,则说明可以通过
		{
			FootPrint(maze, &curpos);//标记已经到过,标记为2
			cur_e.ord = user_step;
			cur_e.seat = curpos;
			cur_e.di = 1;
			Push(&sstack,cur_e);  //压栈,保存当前信息
			if (curpos.x == end.x && curpos.y == end.y) //判定是否到达出口
			{
				break; //到达出口跳出循环
			}
			curpos = NextPos(&curpos,1);  //获取下一个位置,位置改变取决于第二个方向参数
			user_step++;  //步数增加
		}
		else
		{
			if (!IsStackEmpty(&sstack))  //下一个位置不能通过
			{   //将栈顶元素弹出来,改变个方向,再压入,循环到4个方向都不通时
			    //倒着将坐标对应数值改为3,并且弹栈。
			    //如果弹出的元素方向信息不为4,则接着找,否则接着退出。
				Pop(&sstack, &cur_e);  
				while (cur_e.di == 4 && !IsStackEmpty(&sstack))
				{
					MarkFlag(maze, &cur_e.seat);
					Pop(&sstack, &cur_e);
				}
				if (cur_e.di < 4)
				{
					cur_e.di++; //换个方向
					Push(&sstack, cur_e);
					curpos = NextPos(&cur_e.seat, cur_e.di);
				}
			}
		}

	} while (!IsStackEmpty(&sstack));
	printf("-------------------------------\n");
	printf("迷宫路径:\n");
	Print_Maze(maze);
	printf("-------------------------------\n");
	printf("打印迷宫路径:\n");
	///打印步骤
	le = (SElemType*)malloc(sizeof(SElemType) * 1024);
	ll = le;
	while (!IsStackEmpty(&sstack))
	{
		Pop(&sstack, &cur_e);
		*le = cur_e;
		le++;
		n++;
	}
	le--;

	while (n>0)
	{
		printf("第%d步:x=%d,y=%d\n", (*le).ord, (*le).seat.x, (*le).seat.y);
		n--;
		le--;
	}
	//printf("%c\n", *ll);
	free(ll);
	///
	DestoryStack(&sstack);
	return OK;
}
  1. 完整代码
#include<stdio.h>
#include<stdlib.h>
#include"sqstack.h"

void Print_Maze(int* s)
{
	int i, j;
	//打印迷宫
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 10; j++)
		{
			printf("%d ", *(s + i * 10 + j));
		}
		printf("\n");
	}
}

void Init_Maze(int* s)
{
	int i,j;

	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 10; j++)
		{
			*(s + i * 10 + j) = 0;
		}
	}

	for (i = 0; i < 10; i++)
	{
		*(s + i) = 1;  //第一行
		*(s + 9 * 10 + i) = 1;//第10行
		*(s + i * 10) = 1; //第一列
		*(s + i * 10 + 9) = 1; //最后一列
	}

	//其他零星数据块
	*(s + 10 + 3) = 1;	*(s + 10 + 7) = 1;
	*(s + 20 + 3) = 1;	*(s + 20 + 7) = 1;	
	*(s + 30 + 5) = 1;	*(s + 30 + 6) = 1;
	*(s + 40 + 2) = 1;	*(s + 40 + 3) = 1;	*(s + 40 + 4) = 1;
	*(s + 50 + 4) = 1;	
	*(s + 60 + 2) = 1;	*(s + 60 + 6) = 1;
	*(s + 70 + 2) = 1;	*(s + 70 + 3) = 1;	*(s + 70 + 4) = 1;	*(s + 70 + 6) = 1;	*(s + 70 + 7) = 1;	
	*(s + 80 + 1) = 1;
	Print_Maze(s);
}

int Pass(int* maze,PosType* p)
{
	//判断p对应的位置是否有来到过
	if (*(maze + p->y * 10 + p->x) == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void FootPrint(int* maze, PosType* p)
{
	*(maze + p->y * 10 + p->x) = 2;
}

void MarkFlag(int* maze, PosType* p)
{
	*(maze + p->y * 10 + p->x) = 3;
}

PosType NextPos(PosType* p,int di)
{
	switch (di)
	{
	case 1:
		p->x += 1;
		break;
	case 2:
		p->y += 1;
		break;
	case 3:
		p->x -= 1;
		break;
	case 4:
		p->y -= 1;
		break;
	default:
		break;
	}
	
	return *p;
}


Status MazePath()
{
	/*
	迷宫类型:1 为墙体
			  0 为未到过
			  2 为已经到
			  3 为此路不通
	*/
	int maze[10][10];
	SqStack sstack;
	PosType start, end,curpos;
	int user_step = 0;
	SElemType cur_e;
	SElemType* le=NULL;
	SElemType* ll = NULL;
	int n=0;

	printf("初始化迷宫:\n");
	Init_Maze(maze);
	Init_Stack(&sstack);
	//起始坐标
	start.x = 1;
	start.y = 1;
	//出口坐标
	end.x = 8;
	end.y = 8;

	curpos.x = start.x; 
	curpos.y = start.y;
	user_step = 1;
	do
	{
		if (Pass(maze, &curpos)) //判断此节点是否到过
		{
			FootPrint(maze, &curpos);//标记已经到过
			cur_e.ord = user_step;
			cur_e.seat = curpos;
			cur_e.di = 1;
			Push(&sstack,cur_e);
			if (curpos.x == end.x && curpos.y == end.y)
			{
				break; //到达出口跳出循环
			}
			curpos = NextPos(&curpos,1);
			user_step++;
		}
		else
		{
			if (!IsStackEmpty(&sstack))
			{
				Pop(&sstack, &cur_e);
				while (cur_e.di == 4 && !IsStackEmpty(&sstack))
				{
					MarkFlag(maze, &cur_e.seat);
					Pop(&sstack, &cur_e);
				}
				if (cur_e.di < 4)
				{
					cur_e.di++; //换个方向
					Push(&sstack, cur_e);
					curpos = NextPos(&cur_e.seat, cur_e.di);
				}
			}
		}

	} while (!IsStackEmpty(&sstack));
	printf("-------------------------------\n");
	printf("迷宫路径:\n");
	Print_Maze(maze);
	printf("-------------------------------\n");
	printf("打印迷宫路径:\n");
	///打印步骤
	le = (SElemType*)malloc(sizeof(SElemType) * 1024);
	ll = le;
	while (!IsStackEmpty(&sstack))
	{
		Pop(&sstack, &cur_e);
		*le = cur_e;
		le++;
		n++;
	}
	le--;

	while (n>0)
	{
		printf("第%d步:x=%d,y=%d\n", (*le).ord, (*le).seat.x, (*le).seat.y);
		n--;
		le--;
	}
	//printf("%c\n", *ll);
	free(ll);
	///
	DestoryStack(&sstack);
	return OK;
}

int main()
{
	MazePath();
	system("pause");
}

转载自原文链接, 如需删除请联系管理员。

原文链接:(十三)栈的应用 --- 迷宫解题五行八卦阵,转载请注明来源!

0