给一个20×20的迷宫和一个起点坐标,用广度优先搜索填充所有的可到达的格子。
#include<stdio.h>
#include<conio.h>
void readdata();
void init();
void search();
int emptyopen();
int takeoutofopen();
int canmoveto(int,int,int*,int*,int);
int used(int,int);
void addtoopen(int,int);
int a[12][12];
int n=12;
int open[20],head,tail,openlen=20;
int s;
void main()
{
int i,j;
readdata();
init();
search();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%3d",a[i][j]);
printf("\n");
}
}
void search()
{
int u, row, col, r, c, i;
while(!emptyopen())
{
u=takeoutofopen();
row=u/n;
col=u%n;
for(i=0;i<4;i++)
{
if(canmoveto(row,col,&r,&c,i))
{
if(!used(r,c))
{
a[r][c]=1;
addtoopen(r,c);
}
}
}
}
}
int emptyopen()
{
if(head==tail)
return(1);
else
return(0);
}
int takeoutofopen()
{
int u;
if(head==tail)
{
printf("errer: stack is empty");
return(-1);
}
u=open[head++];
head=head%openlen;
return(u);
}
int canmoveto(int row, int col, int *p, int *q, int direction)
{
int r,c;
r=row;
c=col;
switch(direction)
{
case 0: c--;
break;
case 1: r++;
break;
case 2: c++;
break;
case 3: r--;
}
*p=r;
*q=c;
if(r<0||r>=n||c<0||c>=n)
return(0);
if(a[r][c]==0)
return(1);
return(0);
}
int used(int row, int col)
{
if(a[row][col]==0)
return(0);
else
return(1);
}
void addtoopen(int row, int col)
{
int u;
u=row*n+col;
open[tail++]= u;
tail=tail%openlen;
if((head-tail)%openlen==1)
printf("open table overflow");
}
void readdata()
{
int i,j,row,col;
char str[20];
scanf("%d%d",&row,&col);
s=row*n+col;
gets(str);
for(i=0;i<n;i++)
{
gets(str);
for(j=0;j<n;j++)
if(str[j]=='.')
a[i][j]=0;
else
a[i][j]=-2;
}
}
void init()
{
head=0;
tail=1;
open[0]=s;
}