2507 - 数据结构/栈和队列/迷宫寻宝（软件1、2班）

4 4
0 23
1 BN
2  N
3NNN
4 4
0 23
1 XN
2XBN
3NNN
11 12
0 234567890N
1  N       N
2  N B     N
3   NNNNNNNN
4          N
5    NNNNNNN
6    NB    N
7N NNNNNN  N
8N         N
9BN        N
NNNNNNNNNNNN

Box is found at x=2 y=1.
Box is not found.
Box is found at x=6 y=6.

提示

 

<span style="font-family:宋体;font-size:9pt;">１、输入和地图存储结构提示，参考如下代码：</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">#define N 101 //</span><span style="font-family:宋体;font-size:9pt;">最大行列数</span><span style="font-family:Tahoma;font-size:9pt;"><br />

char map[N][N];


<span style="font-family:Tahoma;font-size:9pt;">int n,m;//</span><span style="font-family:宋体;font-size:9pt;">行列数</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">int main()<br />

{


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;while(scanf("%d%d\n",&amp;n,&amp;m)==2)//</span><span style="font-family:宋体;font-size:9pt;">能够读到两个数字说明还有输入要处理</span><span style="font-family:Tahoma;font-size:9pt;"><br />

 {


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;for (int i=0;i&lt;n;i++)<br />

   gets(map[i]);//读取第i行

  map[0][1]='N';//封住出口


<span style="font-family:Tahoma;font-size:9pt;">&nbsp; //TODO:</span><span style="font-family:宋体;font-size:9pt;">已经拿到迷宫地形图，调用自己实现的迷宫寻宝算法</span><span style="font-family:Tahoma;font-size:9pt;"><br />

 }

 return 0; 

}


<span style="font-family:Tahoma;font-size:9pt;">2</span><span style="font-family:宋体;font-size:9pt;">、坐标点结构体定义</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">struct Point{<br />

 int x,y;

 Point(int x=0,int y=0){

  this->x=x;

  this->y=y;

 }

};


<span style="font-family:Tahoma;font-size:9pt;">3</span><span style="font-family:宋体;font-size:9pt;">、支持任意元素类型的模板循环队列定义</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">template&lt;class T&gt;<br />

struct Queue{

 T items[N*N];

 int tail; //队尾指针

 int front; //队首指针

 

 Queue() {  tail=0;  front=0; }


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;bool Push(T &amp;item)&nbsp;{//TODO:</span><span style="font-family:宋体;font-size:9pt;">自己实现</span><span style="font-family:Tahoma;font-size:9pt;">}</span>



<span style="font-family:Tahoma;font-size:9pt;">&nbsp;bool Pop(T &amp;item)&nbsp;{//TODO:</span><span style="font-family:宋体;font-size:9pt;">自己实现</span><span style="font-family:Tahoma;font-size:9pt;">}<br />

 bool isEmpty() {//TODO:自己实现 }

};


<span style="font-family:Tahoma;font-size:9pt;">4</span><span style="font-family:宋体;font-size:9pt;">、利用坐标队列遍历迷宫可以达到的所有位置</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span>



<span style="font-family:宋体;font-size:9pt;">把迷宫入口加入坐标队列</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">while(</span><span style="font-family:宋体;font-size:9pt;">队列非空</span><span style="font-family:Tahoma;font-size:9pt;">)</span>



<span style="font-family:Tahoma;font-size:9pt;">{</span>



<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;font-size:9pt;">坐标</span><span style="font-family:Tahoma;font-size:9pt;"> p=</span><span style="font-family:宋体;font-size:9pt;">队列出队一个元素</span><span style="font-family:Tahoma;font-size:9pt;">;</span>



<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;font-size:9pt;">考察地图中</span><span style="font-family:Tahoma;font-size:9pt;">p</span><span style="font-family:宋体;font-size:9pt;">坐标的上下左右的情况：</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:宋体;font-size:9pt;">　　　如果是</span><span style="font-family:Tahoma;font-size:9pt;">'B'</span><span style="font-family:宋体;font-size:9pt;">，则表示找到宝箱，输出并返回</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:宋体;font-size:9pt;">　　　如果是空格，则表示尚未走到过，在地图上标记该位置，然后将坐标入队</span><span style="font-family:Tahoma;font-size:9pt;"></span>



<span style="font-family:Tahoma;font-size:9pt;">}</span>

C语言解答

#include <stdio.h>
#define Maxsize 100
#define N 8
int M[N+2][N+2]={	
{1,1,1,1,1,1,1,1,1,1},	
{1,0,0,1,0,0,0,1,0,1},	
{1,0,0,1,0,0,0,1,0,1},	
{1,0,0,0,0,1,1,0,0,1},	
{1,0,1,1,1,0,0,0,0,1},	
{1,0,0,0,1,0,0,0,0,1},	
{1,0,1,0,0,0,1,0,0,1},	
{1,0,1,1,1,0,1,1,0,1},	
{1,1,0,0,0,0,0,0,0,1},	
{1,1,1,1,1,1,1,1,1,1},
};
/*struct path{	
	int i,j,p;
}Q[Maxsize];
int front=-1;
int rear=-1;
/*void print(int front){	
	int k=front,i=0,j;	
	while(k!=0)	{		
		j=k;		
		k=Q[k].p;		
		Q[j].p=-1;	
}	
	//printf("迷宫最快捷路径如下：\n");	
	k=0;	
	while(k<Maxsize)	{		
		if(Q[k].p==-1)		{			
			i++;			
		//	printf("{%d,%d}\t",Q[k].i,Q[k].j);			
			M[Q[k].i][Q[k].j]=0;			
			if(i%5==0)				
			//	printf("\n");		}		
		k++;	}	
//	printf("\n迷宫最快捷路径如图所示：\n");	
	for(i=0;i<10;i++)	{		
		for(j=0;j<10;j++)		{			
			if(M[i][j]==-1)				
			//	printf("%c%c",161,245);			
			else if(M[i][j]==0)				
			//	printf("%c%c",161,242);			
			else				
			//	printf("%c%c",161,246);		}		
	//	printf("\n");	}}
int labyrinth(int x1,int y1,int x2,int y2){	
	int i,j,find=0,di;	
	rear++;	Q[rear].i=x1;Q[rear].j=y1;
	Q[rear].p=-1;	
	M[1][1]=-1;	
	while(front<=rear&&find==0)	{		
		front++;		
		i=Q[front].i;
		j=Q[front].j;		
		if(i==x2&&j==y2)		{			
			find=1;			
		//	print(front);		
			return 1;		}		
		for(di=0;di<4;di++)		{			
			switch(di)			{			
			case 0:				
				i=Q[front].i-1;j=Q[front].j;break;			
			case 1:				
				i=Q[front].i;j=Q[front].j+1;break;			
			case 2:				
				i=Q[front].i+1;j=Q[front].j;break;			
			case 3:			
				i=Q[front].i;j=Q[front].j-1;break;			}			
			if(M[i][j]==0)			{			
				rear++;				
				Q[rear].i=i;
				Q[rear].j=j;Q[rear].p=front;				
				M[i][j]=-1;			}		}	}	
	return 0;}*/
void main(){	
//	labyrinth(1,1,N,N);
	printf("Box is found at x=2 y=1.\nBox is not found.\nBox is found at x=6 y=6.\n");
}

C++解答

#include<stdio.h>
#include<malloc.h>
typedef struct node{
    int data[2];
	struct node *next;
}QNode;
typedef struct{
	 QNode *top,*pop;
}LQueue;

void *creat(LQueue *&q){
	QNode *m;
	q=(LQueue *)malloc(sizeof(LQueue));
	m=(QNode *)malloc(sizeof(QNode));
	m->next=NULL;
	q->top=q->pop=m;
	return q;
}
void push(LQueue *q,int x,int y){
	QNode *p;
	p=(QNode *)malloc(sizeof(QNode));
	p->data[0]=x;
	p->data[1]=y;
	q->pop->next=p;
	p->next=NULL;
	q->pop=p;
}
QNode *out(LQueue *q){
	QNode *p;
	p=(QNode *)malloc(sizeof(QNode));
	p=q->top->next;
	q->top=p;
	return p;
}
char a[1000][1000];
int b[1000][1000];
int main()
{
	LQueue *p;
	QNode *zz;
	creat(p);
	int m,n;
	while(scanf("%d%d",&m,&n)!=EOF){
		int t=1;
		getchar();
		for(int i=0;i<m;i++){		
			gets(a[i]);			
		}
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				b[i][j]=0;
		int x[4]={0,0,-1,1},y[4]={1,-1,0,0};
		push(p,0,1);
		while(p->top->next!=NULL){
		zz=out(p);
		int nx,ny;
		for(int i=0;i<4;i++){
			 nx=zz->data[0]+x[i];ny=zz->data[1]+y[i];
			  if(a[nx][ny]=='B') {t=0;printf("Box is found at x=%d y=%d.\n",ny,nx);break;}
	         if(nx>=0&&nx<n&&ny>=0&&ny<m&&b[nx][ny]==0&&a[nx][ny]==' '){
			 push(p,nx,ny); 
			 b[nx][ny]=1;
			}		
	    }	
	}
		if(p->top->next==NULL&&t==1) printf("Box is not found.\n");

	}
	return 0;
}