迷宫问题 by:192132-01 mfcheer

迷宫问题

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

要求：

（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。

（2）测试几组数据，数据的规模由小变大，即网格越来越小，障碍越来越复杂。

（3）实现该问题的可视化界面。

#include<stdio.h>  
#include<iostream>  
#include<math.h>  
#include<stdlib.h>  
#include<ctype.h>  
#include<algorithm>  
#include<vector>  
#include<string.h>  
#include<stack>  
#include<set>  
#include<map>  
#include<sstream>  
#include<time.h>  
#include<utility>  
#include<malloc.h>  
#include<stdexcept>  
#include<iomanip>  
#include<iterator>  

using namespace std;

int n, m, sx, sy, ex, ey, t;
int p[110][110];

int vis[110][110];
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

struct node
{
	int x;
	int y;
};

struct node pre[30][30];//存储节点前一个位置


//////////////////////////  栈
#define DataType node               

struct Node;                       
typedef struct Node *PNode;         

typedef struct Node                 
{
	DataType info;                
	PNode link;                   
}Node;

typedef struct LinkStack           
{
	PNode top;        
}LinkStack;

typedef struct LinkStack * PLinkStack;   
PLinkStack createEmptyStack(void);
int isEmptyStack(PLinkStack stack);
int push(PLinkStack stack, DataType x);
int pop(PLinkStack stack);
DataType getTop(PLinkStack stack);
void showStack(PLinkStack stack);
void setEmpty(PLinkStack stack);
void destroyStack(PLinkStack stack);

PLinkStack createEmptyStack(void)
{
	PLinkStack stack = (PLinkStack)malloc(sizeof(struct LinkStack));
	if (stack == NULL)
		printf("存储分配失败，请重建栈！\n");
	else
		stack->top = NULL;
	return stack;
}
 
int isEmptyStack(PLinkStack stack)
{
	return (stack->top == NULL);
}

int push(PLinkStack stack, DataType x)
{
	PNode p = (PNode)malloc(sizeof(struct Node));
	if (p == NULL)
	{
		printf("新结点分配内存失败，进栈失败，请重试！\n");
		return 0;
	}
	else
	{
		p->info = x;
		p->link = stack->top;     
		stack->top = p;
		return 1;
	}
}
 
int pop(PLinkStack stack)
{
	if (isEmptyStack(stack))
	{
		printf("栈为空！\n");
		return 0;
	}
	else
	{
		PNode p;
		p = stack->top;   //删除最后一个结点  
		stack->top = stack->top->link;
		free(p);
		return 1;
	}
}

DataType getTop(PLinkStack stack)
{
	if (isEmptyStack(stack))
	{
		printf("栈为空！取栈顶元素失败！\n");
	}
	return (stack->top->info);
}

void showStack(PLinkStack stack)
{
	if (isEmptyStack(stack))
		printf("当前栈为空！无内容可显示。\n");
	else
	{
		PNode p;
		p = stack->top;
		printf("顶--> ");
		while (p->link != NULL)
		{
			printf("%d ", p->info);
			p = p->link;
		}
		printf("%d ", p->info);   
		printf("-->底\n");
	}
}

void setEmpty(PLinkStack stack)
{
	stack->top = NULL;
}

void destroyStack(PLinkStack stack)
{
	if (stack)
	{
		stack->top = NULL;
		free(stack);
	}
}
///////////////////////////

int check(int x, int y)
{
	if (x >= 0 && x < m && y >= 0 && y < n)
		return 1;
	return 0;
}

void printf_path()
{
	node ss,sss;
	
	DataType data;
	PLinkStack stack;
	
	stack = createEmptyStack();

	ss.x = 4;
	ss.y = 4;

	while (1)
	{
		push(stack, ss);
		if (ss.x == sx && ss.y == sy)
			break;
		ss = pre[ss.x][ss.y];
	}

	int pres, presy;
	
	while (!(isEmptyStack(stack)))
	{
		ss = getTop(stack);
		pop(stack);
		if (!(isEmptyStack(stack)))
			sss = getTop(stack);
		printf("此刻坐标(%d, %d)  ", ss.x, ss.y);
		
		if (!(isEmptyStack(stack)))
		{
			if (sss.x == ss.x && sss.y == ss.y + 1)
				printf("向右走\n");
			if (sss.x == ss.x && sss.y == sss.y - 1)
				printf("向左走\n");
			if (sss.x == ss.x + 1 && sss.y == sss.y)
				printf("向下走\n");
			if (sss.x == ss.x - 1 && sss.y == sss.y)
				printf("向上走\n");
		}
	}printf("到达终点!\n");
}

////////////////////////队列

#define Error( str )        FatalError( str )
#define FatalError( str )   fprintf( stderr, "%s\n", str ), exit( 1 )
#define  ElementType node

#define MAXQUEUE 100

typedef struct NODE
{
	ElementType data;
	struct NODE* nextNode;
} NODE;
typedef struct queue
{
	NODE* front;    // 对首指针
	NODE* rear;     // 队尾指针
	int items;      // 队列中项目个数

} *ptrQueue;
typedef ptrQueue Queue;
int IsEmpty(Queue q);
int IsFull(Queue q);
Queue CreateQueue(void);
void DisposeQueue(Queue q);
void MakeEmpty(Queue q);
void Enqueue(ElementType x, Queue q);
ElementType Front(Queue q);
void Dequeue(Queue q);

int IsFull(Queue q)
{
	return q->items == MAXQUEUE;
}

int IsEmpty(Queue q)
{
	return q->items == 0;
}
Queue CreateQueue(void)
{
	Queue q;

	q = (Queue)malloc(sizeof(struct NODE));
	if (NULL == q)
		Error("空间不足，队列内存分配失败！");

	q->front = (NODE*)malloc(sizeof(NODE));
	if (NULL == q->front)
		Error("空间不足，队列首节点内存分配失败！");

	q->rear = (NODE*)malloc(sizeof(NODE));
	if (NULL == q->rear)
		Error("空间不足，队列尾节点内存分配失败！");

	q->items = 0;

	return q;
}

void DisposeQueue(Queue q)
{
	MakeEmpty(q);
	free(q);
}

void MakeEmpty(Queue q)
{
	if (q == NULL)
		Error("必须先使用CreateQueue创建队列！");

	while (IsEmpty(q))
		Dequeue(q);
}

void Enqueue(ElementType x, Queue q)
{
	if (IsFull(q))
		Error("队列已满！");

	NODE* pnode;
	pnode = (NODE*)malloc(sizeof(NODE));
	if (NULL == pnode)
		Error("新节点分配内存失败！");

	pnode->data = x;
	pnode->nextNode = NULL;
	if (IsEmpty(q))
		q->front = pnode;           // 项目位于首端
	else
		q->rear->nextNode = pnode;  // 链接到队列尾端
	q->rear = pnode;                    // 记录队列尾端的位置
	q->items++;                     // 项目数加1

	return;
}

void Dequeue(Queue q)
{
	if (IsEmpty(q))
		Error("队列本身为空！");

	NODE* pnode;
	pnode = q->front;
	q->front = q->front->nextNode;
	free(pnode);

	q->items--;
	if (q->items == 0)
		q->rear = NULL;

	return;
}

ElementType Front(Queue q)
{
	if (!IsEmpty(q))
		return q->front->data;
	Error("队列为空\n");
}

ElementType FrontAndDequeue(Queue q)
{
	ElementType x;

	if (IsEmpty(q))
		Error("队列为空！");
	else
	{
		q->items--;
		x = q->front->data;
		q->front = q->front->nextNode;
	}

	return x;
}

///////////////////////

int bfs()
{
	memset(vis, 0, sizeof(vis));

	Queue sqQueue;
	sqQueue = CreateQueue();

	node qq, qqq;

	qq.x = sx;
	qq.y = sy;
	vis[sx][sy] = 1;

	Enqueue(qq, sqQueue);

	while (!IsEmpty(sqQueue))
	{
		qq = Front(sqQueue);
		Dequeue(sqQueue);

		if (qq.x == ex && qq.y == ey)
		{
			printf_path();
			return 1;
		}

		for (int i = 0; i < 4; i++)
		{
			int x = qq.x + dir[i][0];
			int y = qq.y + dir[i][1];

			if (!check(x, y) || vis[x][y] || p[x][y] == 1)
				continue;

			qqq = qq;
			qqq.x = x;
			qqq.y = y;

			pre[qqq.x][qqq.y] = qq;

			vis[x][y] = 1;
			Enqueue(qqq, sqQueue);
		}
	}
	return 0;
}


int main()
{
	printf("请输入地图长和宽\n");
	while (cin >> m >> n)
	{
		printf("输入起点坐标和重点坐标\n");
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		printf("请输入地图\n");
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> p[i][j];
			}
		}
		int ans = bfs();
		if (ans == 0)
			printf("不存在起点到终点的通路\n\n\n\n");
			printf("\n\n\n\n");
		printf("是否继续 1.yes 2.no\n ");
			scanf("%d",&t);
			if (t == 2) { printf("          再见   ,谢谢使用本系统！\n\n\n"); return 0; }
		printf("\n\n\n\n");
		printf("请输入地图长和宽\n");
	}
	return 0;
}

测试数据：

5 5
0 0 4 4
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 1 0

1
5 5
0 0 4 4
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

2