小黑

用户名：20190341315

访问量：8021

签　名：

菜！是真的菜，水题还做不全乎！菜。

等　　级
排　　名	126
经　　验	7718
参赛次数	8
文章发表	25
年　　龄	0
在职情况	学生
学　　校	郑州商学院
专　　业	计算机科学与技术

　　自我简介：

C/C++初学菜鸟

TA的其他文章

蓝桥杯算法提高VIP-统计单词数-题解（C语言代码）
浏览：851

[出圈]-题解（C语言代码）
浏览：411

树查找-题解（C++代码）
浏览：343

你可能喜欢

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

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

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

信息学奥赛一本通T1255-迷宫问题-题解(BFS遍历过程,每个点都记录自己的爸爸;最后,终点->起点：反向找爸爸)

　　作者: 小黑　　　　发表时间：2020-12-12 23:16:58 浏览：549　|　评论：0　

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

### 思路：bfs搜索到最后队列中只有可通过的点;这些点中肯定有一条最短路径;
### 而且肯定是最短路径先到达终点,而且只有最短路径到达了终点(为了确保只有一条路径到达终点,加个判断:到达终点就结束);
### 在结构体定义一个成员：pre；用来存储上一个点(也可以称之为父亲)的下标,第一个点(起点)的父亲下标定义为-1；
### 从终点开始倒着访问(俗称：找爸爸),到起点结束;
```javascript
#include<stdio.h>
#include<string.h>
int a[10][10]={0};//地图
struct st{
    int x;//横坐标
    int y;//纵坐标
    int f;//爸爸下标
    int s;//路径长度;对于这一题没有
    st()//构造函数
    {//成员调用前初始化
        x=0;
        y=0;
        f=-1;
        s=0;
    }
}q[100],s[101];
int book[10][10];//标记矩阵
int next[4][2]={-1,0,1,0,0,1,0,-1};//方向矩阵
int main()
{
    memset(a,1,sizeof(a));
    for(int i=1;i<=5;i++)
    for(int j=1;j<=5;j++)
    scanf("%d",&a[i][j]);//输入矩阵
	/*bfs			*/
    int f=0,r=0;//f:队列头指针;r:队列尾指针
    int x=1,y=1;
    int nx,ny;
	int flag=0;//标记
    q[r].x=1;
    q[r].y=1;
    q[r++].s=1;
    book[x][y]=1;//通过后标记
    while(f!=r)//bfs遍历模板
    {
        x=q[f].x;
        y=q[f].y;
        for(int i=0;i<4;i++)
        {//循环遍历4个方向
            nx=x+next[i][0];
            ny=y+next[i][1];
            if(a[nx][ny]==0&&book[nx][ny]==0)
            {
                book[nx][ny]=1;
                q[r].x=nx;
                q[r].y=ny;
                q[r].f=f;//记录爸爸下标
                q[r++].s=q[f].s+1;//每个点的步数,这一题用不到
                if(nx==5&&ny==5)
                {//到达终点
                    flag=1;//标记
                    break;//内循环结束
                }
            }
        }
        if(flag==1)
        break;//外循环结束,这个必不可少,不然队列最后不一定是终点
        f++;//头指针一定要最后++,不然爸爸下标会多一
    }
    int t=r-1;//队列最后一个点下标
	int k=0;
    while(t!=-1)//起点没爸爸下标是-1;t==-1结束
    {//直接输出是倒序的，所以再用一个数组储存点的坐标
        s[k].x=q[t].x;
        s[k++].y=q[t].y;
        t=q[t].f;//寻找该点的爸爸
    }
    for(int i=k-1;i>=0;i--)//输出
    printf("(%d, %d)\n",s[i].x-1,s[i].y-1);
    return 0;
}
```

0.0分

5 人评分

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

小黑

TA的其他文章

你可能喜欢

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

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

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

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

三进制小数（C++代码）（第11位大于1.5才能进位）

信息学奥赛一本通T1255-迷宫问题-题解(BFS遍历过程,每个点都记录自己的爸爸;最后,终点->起点：反向找爸爸)

评论区

精彩推荐

点我有惊喜！你懂得！

字符串比较（C语言代码）答案错误？？？？

母牛的故事（C语言代码）

【金明的预算方案】（C++代码）

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

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

蚂蚁感冒（C语言代码）

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

蛇行矩阵（C语言代码）

一元一次方程（C语言代码）

小黑

TA的其他文章

你可能喜欢

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

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

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

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

三进制小数 （C++代码）（第11位大于1.5才能进位）

信息学奥赛一本通T1255-迷宫问题-题解(BFS遍历过程,每个点都记录自己的爸爸;最后,终点->起点：反向找爸爸)

评论区

精彩推荐

点我有惊喜！你懂得！

字符串比较 （C语言代码）答案错误？？？？

母牛的故事 （C语言代码）

【金明的预算方案】 （C++代码）

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

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

蚂蚁感冒 （C语言代码）

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

蛇行矩阵 （C语言代码）

一元一次方程 （C语言代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

　　评论区

字符串比较（C语言代码）答案错误？？？？

母牛的故事（C语言代码）

【金明的预算方案】（C++代码）

蚂蚁感冒（C语言代码）

蛇行矩阵（C语言代码）

一元一次方程（C语言代码）