charmmm

用户名：1420462013

访问量：3852

签　名：

少年心怀乌托邦，心仍向阳肆生长

等　　级
排　　名	755
经　　验	3794
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	Bilibili
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-k倍区间
浏览：174

你可能喜欢

A+B for Input-Output Practice (VI) （C++代码）

迷宫问题（C代码）

　　作者: charmmm　　　　发表时间：2022-02-28 13:06:40 浏览：358　|　评论：0　

原题链接：信息学奥赛一本通T1255-迷宫问题

**解题思路**：如何求最短路径？我们可以建立一个队列，过程如下

（1）将起点（0，0）入队，

（2）如果队列为空，则问题无解，退出执行

（3）将当前的队头结点出队，并检查该节点是不是目标节点，若是，则求解成功

（4）若队头结点不可扩展，则转（2） （所谓扩展结点就是当前结点可以一步到达的结点）

（5）然后将队头结点的扩展结点（要判重）依次入队并建立一个node型的二维数组记录扩展结点的前驱节点（因为最后要输出路径），然后转（2）

这个题的关键就是理解BFS算法，怎么保存最短路径以及最短路径的输出。
```c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXQSIZE 10
#define TRUE 1
#define FALSE 0
typedef int boolean;
typedef struct{
	int x；//结点在迷宫中的位置 
    int y;
}node;
typedef struct{
	node *base;
	int front;
	int rear;
}SqQueue;
SqQueue Q;
node pre[10][10];//建立一个node类型的数组来保存每个扩展结点的前驱节点 
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int Visited[5][5];//建立Visited数组来标记走过的路
//*******************队列算法*******************
void InitQueue(SqQueue *Q){//初始化队列
	Q->base=(node *)malloc(MAXQSIZE*sizeof(node));
	if(!Q->base) return;
	Q->front=Q->rear=0;
}
boolean QueueEmpty(SqQueue Q){//判断队列是否为空
	if(Q.front==Q.rear) return TRUE;
	else return FALSE;
}
void EnQueue(SqQueue *Q,node str){//结点入队
	if((Q->rear+1)%MAXQSIZE==Q->front) return;
	Q->base[Q->rear].x=str.x;
	Q->base[Q->rear].y=str.y;
	Q->rear=(Q->rear+1)%MAXQSIZE;
}
void DeQueue(SqQueue *Q,node *m){//结点出队
	if(QueueEmpty(*Q)) return;
	m->x=Q->base[Q->front].x;
	m->y=Q->base[Q->front].y;
	Q->front=(Q->front+1)%MAXQSIZE;
}
void DestoryQueue(SqQueue *Q){//销毁队列
	if(!Q->base) free(Q->base);
	Q->base=NULL;
	Q->front=Q->rear;
	return;
}
//*****************递归输出最短路径****************
void PrintRoad(node str){
	if(str.x==0&&str.y==0){
		printf("(0, 0)\n");
		return;
	}
	PrintRoad(pre[str.x][str.y]);//递归到前驱节点
	printf("(%d, %d)\n",str.x,str.y); 
} 
//********************BFS************************
void BFS(){
	node str;
	str.x=str.y=0;
	Visited[0][0]=1;
	EnQueue(&Q,str);
	while(!QueueEmpty(Q)){
		node now=Q.base[Q.front];//取队首结点且将其出队 
		DeQueue(&Q,&now);
		if(now.x==4&&now.y==4){//找到终点且输出最短路径 
			PrintRoad(now);
			return;
		}
		//扩展结点并入队 
		for(int i=0;i<4;i++){
			node next;
			next.x=now.x+dir[i][0];//向左/右 
			next.y=now.y+dir[i][1];//向下/上
			if(next.x>=0&&next.x<=4&&next.y>=0&&next.y<=4&&!Visited[next.x][next.y]){//判重
				Visited[next.x][next.y]=1;
				EnQueue(&Q,next);
				pre[next.x][next.y]=now;//在当前元素的位置保存它的前驱节点
			}
		}
	}
} 
int main(){
	InitQueue(&Q);
	memset(Visited,0,sizeof(Visited));//初始化Visited数组
	//读入迷宫 
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			scanf("%d",&Visited[i][j]);
		} 
	}
	BFS();
	DestoryQueue(&Q);
	return 0;
}
```
能力有限，多多指教

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

charmmm

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

A+B for Input-Output Practice (VI) （C++代码）

多输入输出练习1 （C语言代码）

迷宫问题（C代码）

评论区

精彩推荐

拆分位数（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1035 题解

C二级辅导-求偶数和（C语言代码）

数列有序（C语言代码）

筛排处理（C语言代码）

发工资咯（C语言代码）

charmmm

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

A+B for Input-Output Practice (VI) （C++代码）

多输入输出练习1 （C语言代码）

迷宫问题（C代码）

评论区

精彩推荐

拆分位数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1035 题解

C二级辅导-求偶数和 （C语言代码）

数列有序 （C语言代码）

筛排处理 （C语言代码）

发工资咯 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

　　评论区

拆分位数（C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

C二级辅导-求偶数和（C语言代码）

数列有序（C语言代码）

筛排处理（C语言代码）

发工资咯（C语言代码）