maze.cpp

教学用的迷宫示例程序

#include<stdio.h>
#define m 10
#define n 15
#define MAX 400
struct node{
		int x,y;//方格点坐标
		int pre; //前趋点指示
};
int maze[m][n]; //迷宫数组
int front,rear;
struct node sq[MAX];//既是纪录搜索路经的数组又是队结构（非循环队）
int zx[8],zy[8];


void printpace(int rear)       //打印迷宫路径           
{
    int i;
	i=rear;
	do
	{
		printf("(%d, %d)<--", sq[i].x, sq[i].y);
		i=sq[i].pre;
	}while(i!=0); 
}

void mazep()                  //搜索迷宫路径
{
	int i, j, x, y, v, front, rear, find;
	sq[1].x=1; sq[1].y=1; sq[1].pre=0;   //从（1， 1）搜索
	find=0;
	front=1; rear=1; maze[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]; j=y+zy[v];  //任选一个方向走
			if(maze[i][j]==0)            //如果该方向可走
			{
				rear++;          //进队
				sq[rear].x=i;
				sq[rear].y=j;
				sq[rear].pre=front;
				maze[i][j]=-1;       //为了避免从头再搜索的赋值
			}
		    if(i==m && j==n)        //找到出口标志
            {
				printpace(rear);
				find=1;
			}
		}
	   front++;
	}
    if(!find)   printf("不存在走出迷宫的路径！\n");
}

void main()
{
	int i, j;
	for(i=1; i<=m; i++)
		for(j=1; j<=n; j++)
		{
			printf("请您输入第%d行第%d列的状态数: 0 或 1\n", i, j);
			scanf("%1d", &maze[i][j]);
		}
    for(i=0; i<=m+1; i++)
    {
		maze[i][0]=1; maze[i][n+1]=1;
	}
	for(j=0; j<=n+1; j++)
	{
		maze[0][j]=1; maze[m+1][j]=1;
	}
    zx[1]=-1;zx[2]=-1;zx[1]=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;
	printf("走出迷宫的路径如下(数字表示迷宫元素状态的下标):\n");
	mazep();
}