数据结构之栈迷宫求解

迷宫求解

头文件

#pragma once
#include <stdbool.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 50
const int Xrange = 12;
const int Yrange = 8;
                                 //坐标结构
typedef struct {
	int Xcoordinate;
	int Ycoordinate;
}PosType;
                                 //迷宫格子的结构
typedef struct {
	PosType Coordinate;
	int Direction;
}Item;
                                    //栈的结构
typedef struct {
	Item * base;
	Item * top;
	int stacksize;
}Stack;

//头文件注释懒得写了，源文件有

bool InitStack(Stack & S);

void ClearStack(Stack & S);

bool DestroyStack(Stack & S);

bool StackEmpty(Stack S);

bool GetTop(Stack S, Item & item);

bool Push(Stack & S, Item item);

bool Pop(Stack & S, Item & item);

PosType NextPos(PosType coor, int direc);

void FailPass(Stack & S, const int pMaze[][Xrange]);

void AddFailPass(Stack & S, PosType coor);

bool PassWay(Stack S,PosType coor,bool (*pcompare)(Item item_a,Item item_b));

bool MazePath(Stack & S1, Stack & S2, PosType start, PosType end);

void PrintfPath(Stack S);

两个栈，一个是路径，一个是不能走的路

#include <cstdlib>
#include <iostream>
#include "convert.h"

//判断当前位置是否能通过，item_a==item_b 返回true否则返回false
bool Compare(Item item_a, Item item_b);

//初始化一个栈，分配定义的STACK_INIT_SIZE个Item大小的空间
bool InitStack(Stack & S)
{
	if (!(S.base = (Item *)new Item[STACK_INIT_SIZE])) exit(1);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return true;
}

void ClearStack(Stack & S)
{
	 S.top = S.base;
}

//获取栈顶元素
bool GetTop(Stack S, Item & item)
{
	if (S.top == S.base)
		return false;
	item = *(S.top - 1);
	return true;
}
//删除栈顶元素
bool Pop(Stack & S, Item & item)
{
	if (S.base == S.top)
		return false;
	item = *(--S.top);
	return true;
}

//添加新的栈顶元素，超出STACK_INIT_SIZE*Item的大小时自动增加STACK_INCREMENT*Item大小的空间
bool Push(Stack & S, Item item)
{
	Item Preitem;
	Item *pnew, *pi;

	if (S.top - S.base >= S.stacksize)   //new有没有像realloc那样的用法呢？这个比较麻烦
	{
		if (!(pnew = (Item *)new Item[STACK_INIT_SIZE + STACK_INCREMENT])) exit(1);
		pi = pnew;
		while (Pop(S, Preitem))      //将数据复制到新的栈中
		{
			*(pi++) = Preitem;
		}
		delete[] S.base;                  //删除旧栈，更改S数据指向新栈
		S.base = pnew;
		S.top = pi;
		S.stacksize = STACK_INIT_SIZE + STACK_INCREMENT;  //更改大小
	}
	*(S.top++) = item;  //添加新的栈顶元素
	return true;
}
                                                 //判断栈S是否为空
bool StackEmpty(Stack S)
{
	return S.base == S.top;
}
                                                 //删除栈S
bool DestroyStack(Stack & S)
{
	delete[] S.base;
	S.base = S.top = nullptr;
	return true;
}
                                                                         //按direc的模式得到下一个位置坐标
PosType NextPos(PosType coor, int direc)
{
	int x,y;
	x = coor.Xcoordinate; y = coor.Ycoordinate;
	switch (direc)
	{
	case 1:return { x , y - 1 };     //1代表向上走
	case 3:return { x , y + 1 };   //3向下
	case 2:return { x + 1, y };   //2向右
	case 4:return { x - 1,  y };   //4向左
	default:
		return { x,y };   //不会发生
	}
}
         //在找通路之前先将所有的设障位置放在一个栈S2中，以后根据S2判断当前位置是否能通过
void FailPass(Stack & S2,const int pMaze[][Xrange])
{
	int x, y;
	Item item;
	for (y = 0;y < Yrange;y++)
		for (x = 0;x < Xrange;x++)
			if (!pMaze[y][x])                 //所有0的地方代表不能通过，记录所有为0的位置的坐标，放在S2中
			{
				item.Coordinate = { x,y };
				item.Direction = 0;
				Push(S2, item);
			}
}
     //走过的位置坐标也添加到S2中，保证不会再次走 错误的道路
void AddFailPass(Stack & S2, PosType coor)
{
	Item item;

	item.Coordinate = coor;
	item.Direction = 0;
	Push(S2, item);
}

//将当前位置和S2中的每一个位置比较，如果都不想等，当前位置可通过，否则不可通过
bool PassWay(Stack S2, PosType coor, bool(*pcompare)(Item item_a, Item item_b))
{
	Item * pi;
	Item item;

	item.Coordinate = coor;
	item.Direction = 0;
	for (pi =S2 .base;pi < S2.top;pi++)
	{
		if ((*pcompare)(item, *pi))     //发现相等的位置，返回false
			return false;
	}  
	return true;    //循环结束也没有发现相等的位置则返回true
}

//S1是最终的通路，S2是设障位置或走过的位置，start，end起点终点
bool MazePath(Stack &S1, Stack &S2, PosType start, PosType end)
{
	Item item;
	PosType coor;

	coor = start;                             //先把起点放入S1中
	item.Coordinate = coor;
	item.Direction = 1;
	if (PassWay(S2, coor, Compare))   //判断起点是否可通过
	{
		AddFailPass(S2, coor);               //可通过则将当前位置放入S2
		Push(S1, item);                           //将item放入S1
		if (coor.Xcoordinate==end.Xcoordinate                 //判断当前位置是否为终点
	&&  coor.Ycoordinate==end.Ycoordinate) return true;
		coor = NextPos(coor, item.Direction);          //当前位置向上走一个单位，进行接下来的判断
	}

	while (!StackEmpty(S1))                       //如果没有找到终点end， S1会一直退栈，最终为空栈
	{
		if (PassWay(S2, coor, Compare))
		{
			item.Coordinate = coor;               //当前位置可通过，添加新的Item到S1中
			item.Direction = 1;
			AddFailPass(S2, coor);            //记录通过的位置，防止以后在来
			Push(S1, item);
			if (coor.Xcoordinate == end.Xcoordinate
				&&  coor.Ycoordinate == end.Ycoordinate) return true;    //判断是否为end
			coor = NextPos(coor,item.Direction);    //当前位置往上走一格，进行下一次判断
		}
		else      //不可以通过的情况
		{
			while(item.Direction == 4)        //如果走到了死胡同的尽头，item的Direction最终会等于4，无路可走
			{                                                 //将该Item从S1中拿掉
				Pop(S1, item);                      
				if (!GetTop(S1, item))             //获取新的栈顶元素，若新的栈顶元素Direction==4
					return false;                         //说明当前位置只能通向刚刚走过的死胡同，因此循环退栈
			}

			if (item.Direction < 4)      //验证当前位置的其他方向能否通过
			{
				coor = item.Coordinate;   //恢复到当前位置
				item.Direction++;            //改变方向
				coor = NextPos(coor, item.Direction);    //新的当前位置
			}
		}
	}
	return false;
}

//S不为空则打印S1代表的路径
void PrintfPath(Stack S)
{
	int x, y;
	char Path[Yrange][Xrange] = {'\0'};    //新建一个和迷宫格数相等的二维char数组Path
	Item * pi;

	if (StackEmpty(S))                                //空
		std::cout << "这个迷宫没有通路";
	else
	{
		for (pi = S.base;pi < S.top;pi++)
		{                                                                                //S1中各元素对应的坐标表现在Path中
			Path[pi->Coordinate.Ycoordinate][pi->Coordinate.Xcoordinate] = '#';
		}
		for (y = 0;y < Yrange;y++)
		{
			for (x = 0;x < Xrange;x++)                 
				if (Path[y][x] == '#')             //用‘#’代表路径
					std::cout << '#';
				else                                     
					std::cout << ' ';
			std::cout << std::endl;
		}
	}
}
//比较坐标是否相等
bool Compare(Item item_a, Item item_b)
{
	if (item_a.Coordinate.Xcoordinate == item_b.Coordinate.Xcoordinate
		&& item_a.Coordinate.Ycoordinate == item_b.Coordinate.Ycoordinate)
		return true;
	else
		return false;
}

先左上角到右下角，之后左上角到右上角

#include <iostream>
#include "convert.h"

int main()
{
	Stack S1, S2;     //S1放路径  S2放不能通过的位置
	InitStack(S1);
	InitStack(S2);
	                            //0代表路障1代表通路
	const int Maze[Yrange][Xrange] = {
		{ 0,0,0,0,0,0,0,0,0,0,0,0 },
		{ 0,1,1,0,1,1,1,0,1,0,1,0 },
		{ 0,1,1,0,1,0,0,0,1,1,1,0 },
		{ 0,0,1,1,1,0,0,1,0,1,0,0 },
		{ 0,1,0,1,0,1,0,1,0,1,0,0 },
		{ 0,1,0,1,1,1,1,1,1,1,0,0 },
		{ 0,1,1,1,0,0,0,0,0,1,1,0 },
		{ 0,0,0,1,1,1,1,1,1,1,1,0 }
	};
	                                    //先记录路障的位置
	FailPass(S2, Maze);
	MazePath(S1, S2, { 1,1 }, { 10,7});  //从左上角到右下角
	PrintfPath(S1);
	std::cout << std::endl;

	ClearStack(S1);
	ClearStack(S2);

	FailPass(S2, Maze);                            //从左上角到右上角
	MazePath(S1, S2, { 1,1 }, { 10,1 });
	PrintfPath(S1);

	DestroyStack(S1);
	DestroyStack(S2);
	return 0;
}

顺着 '#' 出发

数据结构之栈迷宫求解

http://download.csdn.net/detail/biqigu/9620926 代码下载

数据结构之栈迷宫求解

迷宫求解

继续阅读

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

回溯法迷宫求解

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器