贝壳找房 · dfs · 算法编程题
贝壳找房 dfs 时限 1 秒 / 256 MB

题目描述

有一片 5*5 的网格，每个网格上有一个 [1,9] 之间的正整数。
从网格中的任意位置出发，四个方向都可以走，走过的位置也可以再走。
走了 5 次之后，经过的位置会形成一个 6 位数，最多可以形成多少个不同的 6 位数呢？

输入输出

输入描述
5 行 5 列共 25 个数
保证输入的数都在 [1,9] 之间
输出描述
一行一个整数表示答案

样例共 3 组

样例 1 · 只有 111111这一种可能的6位数
输入
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1
输出
1
样例 2 · 一共15种可能的6位数 111111 111112 111121 111211 111212 112111 112121 121111 121112 121211 121212 211111 211121 212111 212121
输入
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
2 1 1 1 1
输出
15
样例 3
输入
1 8 1 9 2
7 1 1 7 2
4 7 3 3 9
7 6 9 5 9
2 3 9 6 7
输出
6498

算法解析依据充分

考点：dfs

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：dfs

本题切入点

5×5 网格走 5 步，规模极小（25×4⁵），直接 DFS 枚举所有路径并去重统计不同的 6 位数。

一条路走到底再回溯，适合枚举全部方案与连通性判定。

思路框架（dfs 通法 · 非本题专属）

  1. 定义递归函数（当前状态、已选集合、累计答案）。
  2. 写终止条件，达到终止条件时结算答案。
  3. 枚举下一步的所有选择，做选择 → 递归 → 撤销选择（回溯）。
  4. 大规模的连通块统计可用 DFS/BFS 染色标记。

实现要点：回溯时务必把状态恢复干净；必要时加剪枝（可行性剪枝、最优性剪枝）。

复杂度：时间 O(状态数) ｜ 空间 O(递归深度)

该范式的通法易错点

  • 回溯时忘记撤销状态，答案被污染。
  • 没有剪枝导致指数级爆炸超时。

样例解读

样例 1：输入 1 1 1 1 1 / 1 1 1 1 1 / 1 1 1 1 1 / 1 1 1 1 1 / 1 1 1 1 1 → 输出 1

只有 111111这一种可能的6位数

样例 2：输入 1 1 1 1 1 / 1 1 1 1 1 / 1 1 1 1 1 / 1 1 1 1 1 / 2 1 1 1 1 → 输出 15

一共15种可能的6位数

111111

111112

111121

111211

111212

112111

112121

121111

121112

121211

121212

211111

211121

212111

212121

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：【2023】贝壳找房春招前端工程师笔试卷2；【2023】贝壳找房春招测试开发工程师笔试卷2。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解