yxy

用户名：dotcpp0787179

访问量：491

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：34

你可能喜欢

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

bfs之迷宫问题--输出路径/但是本题数据有错

　　作者: yxy　　　　发表时间：2024-09-12 15:03:09 浏览：31　|　评论：1　

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

# 使用对组数列存储路径并使用栈反向输出
迷宫问题大家都很熟悉了 一眼就看出用bfs宽搜出最短路即可 但是如何输出每个最短路径呢？
###### 使用对组数组更新实时最短路径 ， 但是因为跟新路径会从后往前存 ， 所以可以用栈来输出（在迷宫大于5*5的时候 适用一点）；

###### 不能使用每次得到的最短步 作为数组下表来存 因为和当前相同步数的路径不止一个 后走到的会覆盖掉前一个数据 ，。

# update : 经过测试发现 本体数据有问题 存在多解 但是答案却是固定 按照从下开始顺时针能AC 但是 逆时针就是WA 希望本题快点加强数据
上代码：
###### code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;
#define int long long   //个人习惯
typedef pair<int , int> PII;
const int N = 10;
int g[N][N];
PII ans[N][N];
int d[N][N];
queue<PII> q;
bool ch[N][N];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1}; //方向数组 用于bfs查询

void bfs(int x , int y)
{
    q.push({x , y});			//起点进队

while (!q.empty())
    {
        PII t = q.front();
        q.pop();		//记得一定要出队 我刚学的时候 老是忘

for (int i = 0 ; i < 4 ; i ++ )
        {
            int xx = t.first + dx[i] , yy = t.second + dy[i];
            if (xx >= 0 && xx <= 4 && yy >= 0  && yy <= 4 && g[xx][yy] == 0 && !ch[xx][yy])
            {
                ch[xx][yy] = true;
                d[xx][yy] = d[t.first][t.second] + 1;  //存最短步数 ，和本题无关
                ans[xx][yy] = t;   // 路径更新
                q.push({xx , yy});
            }
        }
    }

int xx = 4 , yy = 4;		//转存路径
    printf("(0, 0)\n"); //先输出起点
    stack<PII> st;
    while (xx || yy)
    {
        st.push({xx ,yy});
        // printf("(%d, %d)\n" , xx , yy);
        PII t = ans[xx][yy];
        xx = t.first , yy = t.second;
    }
    while (!st.empty())		//栈输出
    {
        PII t = st.top();
        printf("(%d, %d)\n" , t.first , t.second); //记住这个空格 必须有
        st.pop();		//一样 记得出栈
    }

}

signed main()
{
    for (int i = 0 ; i < 5 ; i ++ )
        for (int j = 0 ; j < 5 ; j ++ ) cin >> g[i][j];

ch[0][0] = true;  //标记起点已经走过 不然会多走？
    bfs(0 , 0);

return 0;

}
```

### 题解不易 点点赞

0.0分

2 人评分

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

　　评论区

109徐守佳

神犇

2024-09-12 15:51:53

yxy

TA的其他文章

你可能喜欢

一个简单易懂的代码

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

求圆的面积（C++代码）这里推荐使用宏定义

点我有惊喜！你懂得！

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

bfs之迷宫问题--输出路径/但是本题数据有错

评论区

精彩推荐

钟神赛车（C语言代码）

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

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

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

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

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

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

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

Cylinder （C语言描述，蓝桥杯）

C语言训练-数字母（C语言代码）

yxy

TA的其他文章

你可能喜欢

一个简单易懂的代码

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

求圆的面积 （C++代码）这里推荐使用宏定义

点我有惊喜！你懂得！

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

bfs之迷宫问题--输出路径/但是本题数据有错

评论区

精彩推荐

钟神赛车 （C语言代码）

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

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

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

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

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

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

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

Cylinder （C语言描述，蓝桥杯）

C语言训练-数字母 （C语言代码）

求圆的面积（C++代码）这里推荐使用宏定义

　　评论区

钟神赛车（C语言代码）

C语言训练-数字母（C语言代码）