蓝桥杯2024年第十五届省赛B组c++复盘 

这一次比赛发挥得相当烂,可以说code水平跟去年比赛发挥相比没有太大变化。

这回比赛前有同学问我准备得怎么样,我说我基本没有准备,同学还不相信,其实确实没认真准备(哭)

F.数字接龙复盘

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏,游戏在一个大小为N × N 的格子棋盘上展开,其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下:
1. 从左上角 (0, 0) 处出发,目标是到达右下角 (N − 1, N − 1) 处的格子,每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

2. 对于路径经过的棋盘格子,按照经过的格子顺序,上面的数字组成的序列要满足:0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。

3. 途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。

4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1),那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

为了方便表示,我们对可以行进的所有八个方向进行了数字编号,如下图2 所示;因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示,如下图 1是一个迷宫示例,它所对应的答案就是:41255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径,输出字典序最小的那一个;如果不存在任何一条路径,则输出 −1。
输入格式
第一行包含两个整数 N、K。接下来输入 N 行,每行 N 个整数表示棋盘格子上的数字。
输出格式
输出一行表示答案。如果存在答案输出路径,否则输出 −1。
样例输入
复制
3 3 0 2 0 1 1 1 2 0 2
样例输出
复制
41255214
提示
【样例说明】行进路径如图 1 所示。
【评测用例规模与约定】对于 80% 的评测用例:1 ≤ N ≤ 5。对于 100% 的评测用例:1 ≤ N ≤ 10,1 ≤ K ≤ 10。

对于这题是一个标准的dfs走迷宫,可惜比赛时浪费时间,加上dfs不熟练,没有写完。

这回我的错误在:dfs的传入传出参数不应该用于传递整体图,返回不应该直接传出结果

介绍dfs:

dfs为深度优先搜索,是较为暴力的一种求解方法,通过一个一个试错然后得到正确答案。

例如:我要从数字1走到数字4,每一次移动,只能进行上下左右选其一移动走一格,怎么走。

1 2

4 3

当我们从数字1上,想找到数字2,对于程序,它并不知道它该往哪走,这就时候就一个一个从上下左右走一遍进行尝试(上下左右走的顺序可自定义)。程序开始尝试往上边走一格,它发现是边界,退回数字1的位置;然后开始尝试往下边走一格,发现是数字3,不符合要求,退回;然后继续尝试往左边走一格,发现是边界,不符合要求,退回;最后往右边走,发现符合要求,于是进入到数字2。

进入数字2后,经过试错退回,找到正确道路是往下走到达数字3,然后往左走到达数字4的终点,最后程序就返回成功到达终点的消息,但是如果程序走完所有能走的路线后还是不能完成目标,就应该返回失败的消息。

可以看看下面的动画理解一下dfs:

当然,如果刚刚接触,我觉得不需要很深入理解概念,只需要记住dfs就是发现正确的路就一直走,只有碰到错误时才会往回退后。更深入的理解多做题就明白了。

由上面的例子可以知道,dsf最关键的几个因素:是否到达目标点、是否走向错误、下一个要移动的方向、记录已经移动过的位置(防止走过的路重新走一遍)

下面是dfs的模板:

function dfs(当前传入状态){

if(当前状态 == 错误状态){
        return 结束错误
    }
	if(当前状态 == 目的状态){
        return 返回成功信息
    }

    for(寻找新状态){
        if(状态合法){
            vis[标记访问该点];
            dfs(新状态1);//遍历时,递归并传入下一个通向的状态
            dfs(新状态2);
            dfs(新状态3);
            dfs(新状态4);
            ?是否需要恢复现场->vis[复原访问标记,表示没来过]
        } 
    }

    //上面运行完后,到达此处说明已经找不到新的状态了,因为在每一次遍历不断递归进入新的dfs,如果有错误和成功会直接触发开头的if条件,从而返回前一步,继续寻找递归其他可能性,只有当所有可能性都被退回,才会到达此处。

return 找不到匹配结果,结束

}

int main()
{
     dfs(初始状态);
}
博客内容均系原创,未经允许严禁转载!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇