1 条题解

  • 0
    @ 2025-2-14 21:22:42

    C :

    #include <stdio.h>
    #include <malloc.h>
    
    #define M 50 // 迷宫行数(包括外墙)
    #define N 50 // 迷宫列数(包括外墙)
    
    #define D 4 // 移动方向数
    
    struct
    {
    	int x,y;
    	#if D==4
    }move[D]={{0,1},{1,0},{0,-1},{-1,0}};
    #endif
    
    // 元素类型
    typedef struct
    {
      int x,y; // 当前点的行值,列值
      int pre; // 前一点在队列中的序号
    } QElemType;
    
    #define MAXQSIZE 251 // 最大队列长度(对于循环队列,最大队列长度要减1) 
    
    typedef struct
    {
    	QElemType *base;// 初始化的动态分配存储空间 相当于一个数组 
    	
    	int front;
    	 
    	int rear;
    }SqQueue;
    
    
    //初始化队列为空
    int InitQueue(SqQueue *Q)
    {
    	Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); 
    	if(!Q->base) return 0;
    	
    	Q->front=Q->rear=0; 
    	return 1;
    }
    
    // 判断队列是否为空
    int QueueEmpty(SqQueue Q)
    {
    	if(Q.front==Q.rear) 
    		return 1;
    	else
    		return 0;
    }
    
    
    // 入队
    int EnQueue(SqQueue *Q,QElemType e)
    {
    	if((Q->rear+1)%MAXQSIZE == Q->front)  return (0);//队列满
    	Q->base[Q->rear] = e;//从队尾插入元素
    	Q->rear = (Q->rear+1) % MAXQSIZE;
    	return 1;
    }
    
    // 出队
    int DeQueue(SqQueue *Q,QElemType *e)
    {
    	if(Q->front == Q->rear) return 0;// 队列空
    
    	*e=Q->base[Q->front];
    	Q->front=(Q->front+1)%MAXQSIZE;
    	return 1;
    }
    
    
    // 广度搜索法求一条迷宫路径
    int Path(char maze[M][N])
    {
    	SqQueue q; 
    	QElemType cur,next; // 当前点和下一点
    	int i,flag=1; // 当找到出口,flag=0
    	int x1, y1;  // 终点的坐标
    
    	//当前点入口为(0,0)点
    	cur.x=0;
    	cur.y=0;
    		
    	cur.pre = -1; // 设入口(第一点)的上一点的序号=-1   
    	maze[cur.x][cur.y] = -1; // 初始点设为已访问过
    
    	InitQueue(&q); 
    	EnQueue(&q,cur); // 起点入队 
    
    	while(!QueueEmpty(q)&&flag) 
    	{ 
    		DeQueue(&q,&cur); // 出队qf为当前点 
    
    		for(i=0;i<D;i++) // 向各个方向尝试 
    		{ 
    			// 下一点的坐标,正东起顺时针4个方向
    			next.x=cur.x+move[i].x; 			
    			next.y=cur.y+move[i].y; 
    
    			if(maze[next.x][next.y] == ' ') 
    			{ 
    				maze[next.x][next.y] = -1; // 已访问过
    				next.pre=q.front-1;
    				EnQueue(&q,next); 	// 将下一点入队				
    			} 
    			if(maze[next.x][next.y] == 'B') 	// 到达终点
    			{ 
    				flag=0; 
    				x1=next.y;
    				y1=next.x;
    				break; 
    			} 
    		} 
    	} 
    	if(flag) // 搜索完整个队列还没到达终点
    	{
    		printf("Box is not found.\n");
    		return 0;
    	} 
    	else
    	{ 
    		printf("Box is found at x=%d y=%d.\n",x1,y1);
    		return 1;    
    	}  
    }   
    
    int main() 
    {  
    	int n,m;  
    	char map[M][N]; // 迷宫数组 
    	
    	while(scanf("%d%d\n",&n,&m)==2) //能够读到两个数字说明还有输入要处理
    	{
    		for (int i=0;i<n;i++) gets(map[i]);//读取第i行
    		Path(map);
    	}
    	return 0;
    }
    
    

    C++ :

    #include "stdio.h"
    #define N 101 //最大行列数
    char map[N][N];
    int n,m;//行列数
    
    struct Point{
    	int x,y;
    	Point(int x=0,int y=0){
    		this->x=x;
    		this->y=y;
    	}
    };
    
    template<class T>
    struct Queue{
    	T items[N*N];
    	int tail;	//队尾指针
    	int front;	//队首指针
    	
    	Queue()
    	{
    		tail=0;
    		front=0;
    	}
    
    	bool Push(T item)
    	{
    		int next=(tail+1)%(N*N);
    		if (next==front)
    			return false;//队满
    		items[tail]=item;
    		tail=next;
    		return true;
    	}
    
    	bool Pop(T &item)
    	{
    		if (front==tail)
    			return false;//队空
    		item=items[front];
    		front=(front+1)%(N*N);
    		return true;
    	}
    	bool isEmpty()
    	{
    		return front==tail;
    	}
    };
    
    bool test(Queue<Point> &points,int x,int y)
    {
    	if (map[y][x]=='B')
    	{
    		printf("Box is found at x=%d y=%d.\n",x,y);
    		return true;
    	}
    	if (map[y][x]==' ')
    	{
    		map[y][x]='G';
    		points.Push(Point(x,y));
    	}
    	return false;
    }
    
    void mazz()
    {
    	Queue<Point> points;
    	map[0][1]='W';
    	points.Push(Point(1,1));
    	int k=0;
    	while(points.isEmpty()==false&&k++<300)
    	{
    		Point p;
    		points.Pop(p);
    		
    		if (map[p.y][p.x]=='B')
    		{
    			return;
    		}
    		if (test(points, p.x-1,	p.y)) return;
    		if (test(points, p.x+1,	p.y)) return;
    		if (test(points, p.x,p.y-1)) return;
    		if (test(points, p.x,p.y+1))return;
    	}
    	printf("Box is not found.\n");
    }
    
    /*
    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
    */
    int main()
    {
    
    	while(scanf("%d%d\n",&n,&m)==2)//能够读到两个数字说明还有输入要处理
    	{
    
    		for (int i=0;i<n;i++)
    			gets(map[i]);//读取第i行
    		map[0][1]='N';//封住出口
    		mazz();
    	}
    	return 0; 
    } 
    
    • 1

    信息

    ID
    871
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者