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

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 12 MB

<span style="font-family:宋体;">实验目的：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　１、熟悉队列的实现和使用；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　２、掌握一种路径搜索算法；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">实验原理：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　１、队列的原理：略</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　２、路径搜索算法的原理：利用队列记忆已经达到过，但还未展开搜索的地点，可以将所有地点无遗漏无重复的搜索到。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">实验步骤：</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　１、定义坐标点类；</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　２、定义实现循环队列类，该类要求可以存储若干个坐标点。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　３、利用队列实现路径搜索算法。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">　　４、完成输入输出控制。</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

题目输入

<span style="font-family:宋体;">输入由多个迷宫组成，每个迷宫开始一行是两个数字</span><span style="font-family:'Microsoft Yahei';">n</span><span style="font-family:宋体;">和</span><span style="font-family:'Microsoft Yahei';">m</span><span style="font-family:宋体;">，表示迷宫的行列数量</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">接下来的</span><span style="font-family:'Microsoft Yahei';">n</span><span style="font-family:宋体;">行是迷宫的字符图案</span>

<span style="font-family:宋体;">图案中的字符</span><span style="font-family:'Microsoft Yahei';">B</span><span style="font-family:宋体;">表示可能的宝箱，空格表示可以走动的空间，其它字符表示障碍物</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">图案的行列坐标是以</span><span style="font-family:'Microsoft Yahei';">0</span><span style="font-family:宋体;">开始计算的，坐标</span><span style="font-family:'Microsoft Yahei';">x=1,y=0</span><span style="font-family:宋体;">处一定是迷宫出入口</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

题目输出

<span style="font-family:宋体;">对应每个迷宫，应该有一行输出</span><span style="font-family:'Microsoft Yahei';"> <span></span></span>

<span style="font-family:宋体;">如果找到宝箱，输出为：</span><span style="font-family:'Microsoft Yahei';">Box is found at x=</span><span style="font-family:宋体;">宝箱</span><span style="font-family:'Microsoft Yahei';">x</span><span style="font-family:宋体;">坐标</span><span style="font-family:'Microsoft Yahei';"> y=</span><span style="font-family:宋体;">宝箱</span><span style="font-family:'Microsoft Yahei';">y</span><span style="font-family:宋体;">坐标</span><span style="font-family:'Microsoft Yahei';">. </span>

<span style="font-family:宋体;">如果找不到宝箱，输出为：</span><span style="font-family:'Microsoft Yahei';">Box is not found. </span>

输入/输出样例

输入格式

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.

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;
}

上一题下一题提示代码讨论统计