migong.cpp

这小程序可以巩固数据结构中栈的知识

#include <stdio.h>
#define m 10 //行数
#define n 15 //列数
struct stype
{
	int x,y,pre;
}sq[400];
int mg[m+1][n+1];
int zx[8],zy[8];
void jiemian();
void printlj(int rear)
{
	int i;
	i=rear;
	do
	{
		printf("(%d,%d)",sq[i].x,sq[i].y);
		i=sq[i].pre;
	}while(i!=0);
}
void mglj()
{
	int i,x,y,j,v,front,rear,find;
	sq[1].x=1;sq[1].y=1;sq[1].pre=0; //从（1，1）开始搜索
	find=0;
	front=1;
	rear=1;
	mg[1][1]=-1;
	while(front<=rear&&!find)
	{
		x=sq[front].x;
		y=sq[front].y;
		for(v=1;v<=8;v++)  //循环扫描每个方向
		{
			i=x+zx[v];   //选择一个前进方向（i,j）
			j=y+zy[v];
			if(mg[1][1]==0)//如果该方向可走
			{
				rear++;  //进入队列
				sq[rear].x=i;
				sq[rear].y=j;
				sq[rear].pre=front;
				mg[i][j]=-1;   //将其值副-1，以避免回过来重复搜索
			}
			if(i==m&&j==n) //找到出口
			{
				printlj(rear);
				find=1;
			}
		}
		front++;
	}
	if(!find)
	{
		printf("                     你的迷宫不存在路径!\n\n");

	}
}
void jiemian()
{

	printf("\n\n\n\n");
	printf("请输入10行15列迷宫数字(只能为0或1!可按空格键对齐数字以使其成矩阵)");
	printf("\n\n");
	printf("                                 迷宫求解\n");
	printf("               ***********************************************\n");
	//printf("                                   ");
	int i,j;
	for(i=1;i<=m;i++) //获取迷宫数据，输入0或1
		for(j=1;j<=n;j++)
			scanf("%ld",&mg[i][j]);
	printf("               ***********************************************\n");
	for(i=0;i<=m+1;i++)//添加外围墙封闭
	{
		mg[i][0]=1;
		mg[i][n+1]=1;
	}
	for(j=0;j<=n+1;j++)
	{
		mg[0][j]=1;
		mg[m+1][j]=1;
	}
	zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
	zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
	mglj();
}



void main()
{jiemian();
}