1 条题解

  • 0
    @ 2024-12-24 9:48:47

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

    信息

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