广度搜索迷宫.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 88 行

#include<stdio.h>
int qh,qe,qee,visited[100];//qee是qe的复制品，用qe的值，但不改变qe,此题未用visited[100]，而是用maze[8][8]来记录访问标记
struct {int x,y,pre;}sq[100];
int maze[8][8]={
					{0,0},
					{0,1,1,1,1,0,1,0},
					{0,0,0,0,1,0,1,0},
					{0,1,0,0,0,0,1,0},
					{0,1,0,1,1,0,1,0},
					{0,1,0,0,0,0,1,1},
					{0,1,0,0,1,0,0,0},
					{0,1,1,1,1,1,1,0}
				};
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};
void out()
{
	int i,j;
	printf("\n\n");
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
		{
			
			if(maze[i][j]==4)
			{
				printf("*");
			}
			else
			{
				printf("%d",maze[i][j]);
			}
			if(j==7)
			{
				printf("\n");
			}
		}
}
int check(int i,int j)
{
	
	if(i>7||i<0||j>7||j<0)
	{
		return 0;
	}
	else if(maze[i][j]!=0)
	{
		return 0;
	}
	else 
	{
		return 1;
	}
}

main()
{
	qe=0;
	qh=-1;
	sq[0].x=sq[0].y=0;
	sq[0].pre=-1;
	while(qh!=qe)
	{
		qh++;
		for(int k=0;k<4;k++)
		{
			if(check(sq[qh].x+fx[k],sq[qh].y+fy[k]))
			{
				qe++;
				sq[qe].x=sq[qh].x+fx[k];
				sq[qe].y=sq[qh].y+fy[k];
				sq[qe].pre=qh;
				maze[sq[qe].x][sq[qe].y]=2;
				if(sq[qe].x==7&&sq[qe].y==7)
				{
					qee=qe;
					while(sq[qee].pre!=-1)
					{
						maze[sq[qee].x][sq[qee].y]=4;
						qee=sq[qee].pre;//不可在此改变qe
					}
					maze[sq[qee].x][sq[qee].y]=4;
					out();
				}
			}
			
		}
	}
}