【更新:增加了简单版本】不寻常的贪吃蛇 ——B 站有奖问答题

B站有奖答题 karb0n ⋅ 于 2021-02-02 16:58:53 ⋅ 最后回复由 karb0n 2021-02-22 23:48:20 ⋅ 449 阅读

B 站原视频地址:https://www.bilibili.com/video/BV1L54y1W7mz

“不寻常的贪吃蛇”

在如下一个 10×10 的贪吃蛇地图中,有一条蛇 S (Snake),但是呢,这条蛇和常见的《贪吃蛇》游戏中的蛇不同,它不想吃果果,只想走过更多格子,寻找宇宙和万物的回答。

file

这条蛇有四个特点:

  1. 它自己在某一时刻只会位于一个格子内;
  2. 它每步只能 “向左”、“向右”、“向上” 或 “向下” 移动一格,且不能越出地图边界;
  3. 它从不会踏上已经去过的格子,已经去过的格子在地图中标注为 V (Visited);
  4. 它的体力是有限的,体力 ≤ 0 就要休息了,地图中的数字表示踏上当前格子会让蛇消耗的体力,数字为负值表示踏上这一格会给蛇增加体力。

蛇走了一段路后,当前的体力值为 42,正在思考一条最好的路线。

请帮它来算一算,它在休息之前,接下来最多可以新踏上多少个格子?(答案为一个数字,如果可以附上你的计算方法会更好)

// 如果你想编程来计算,下边的文字会便于你复制地图写进代码:
8, 7, 7, 8, 2, 8, -2, 0, 5, -5
-1, 3, 0, -4, 6, -2, 8, -2, 8, -4
4, -4, V, V, 3, V, V, 4, -2, 0
0, -6, V, V, 9, V, V, -3, 4, 3
-6, 0, V, V, V, V, V, 6, -2, -1
-2, 2, V, -4, V, V, V, -5, -4, 5
7, 6, V, -6, 2, 5, V, -2, -1, 1
-2, 8, V, 5, 2, 9, S, 6, 8, 4
1, -5, 9, 5, 0, 2, -2, -4, 5, 1
-6, -2, 9, -2, 6, -1, 2, 0, 9, -2

【2021-2-13更新】
由于地图中含负值,难度是较大的,于是我们增加了地图如下的简单版本。完成简单版本的解答同样有机会参与抽取开发板。

// 不含负值的简单版本
8, 7, 7, 8, 2, 8, 2, 0, 5, 5
1, 3, 0, 4, 6, 2, 8, 2, 8, 4
4, 4, V, V, 3, V, V, 4, 2, 0
0, 6, V, V, 9, V, V, 3, 4, 3
6, 0, V, V, V, V, V, 6, 2, 1
2, 2, V, 4, V, V, V, 5, 4, 5
7, 6, V, 6, 2, 5, V, 2, 1, 1
2, 8, V, 5, 2, 9, S, 6, 8, 4
1, 5, 9, 5, 0, 2, 2, 4, 5, 1
6, 2, 9, 2, 6, 1, 2, 0, 9, 2
成为第一个点赞的人吧 :bowtie:
回复数量: 6
  • karb0n 突然发现,我发的帖子全是软件安装方法
    2021-02-02 17:10:45

    哇哇哇这题好有意思 我要赶快做

  • karb0n 突然发现,我发的帖子全是软件安装方法
    2021-02-11 21:20:17

    有想法欢迎在这个版中留下评论一起讨论 :sob:

  • 花酒石
    2021-02-20 14:42:20

    回溯求解:

    第一个可能是65,解空间太大,程序运行太慢,又不太好记忆优化,用多线程解会更快点吧。65是到目前为止找到的最大的长度。

    第二个简单,最大是20

  • 滕氏蓝
    2021-02-22 23:21:09

    贴一下代码,复杂版的出不来55 希望大佬们指导

    snack_map = []
    for i in snack_map_str.split("\n"):
        snack_map.append(i.split(", "))
    #产生一个行列列表
    
    def move_snake(x,y,vitality):
        if vitality>0:
            next_step=[(x+1,y),(x,y+1),(x-1,y),(x,y-1)]
            steps = [0]
            for i in range(4):
                if (next_step[i][0] in range(10) and 
                    next_step[i][1] in range(10) and
                    snack_map[next_step[i][0]][next_step[i][1]] != "V"):
                    snack_map_temp = snack_map[x][y]
                    snack_map[x][y] = "V"
                    steps.append(move_snake(next_step[i][0],next_step[i][1],vitality-int(snack_map[next_step[i][0]][next_step[i][1]])))
                    snack_map[x][y] = snack_map_temp
                    # 递归一直走 要修改列表所以要暂存原本格子
                else: continue
            # 循环四个方向
            return max(steps) + 1
            # 返回四个方向最大步数
        else:
            return 0
        #没体力了走不返回0
    
    print("最远路径:",move_snake(7,6,42)-1)
    # 算上了初始格子所以要减去1
  • karb0n 突然发现,我发的帖子全是软件安装方法
    2021-02-22 23:46:41

    @花酒石
    没错!普通难度是比较难找到“全局最优解”的,65就是一个近似最优解。简单版本的全局最优解确实是20!

  • karb0n 突然发现,我发的帖子全是软件安装方法
    2021-02-22 23:48:20

    @滕氏蓝
    复杂版的确实不容易获得全局最优解,可以尝试在运行指定次数后停止,就有机会获得一个近似优解。

暂无评论~~
  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
Ctrl+Enter