页面加载中…
K0066. 魔法寻宝任务
中等通过率 78% · 提交 40 · 通过 31
DFS可信回溯
华为可信认证科目一方向改编 · 聚焦「DFS / 可信」 · 难度：中等
在魔法城堡的中心，有一座古老的神秘房间，房间里隐藏着一件珍贵的宝物。为了获得这份宝藏，你需要帮助勇士们完成一项任务：他们必须从一个特定的起点开始，寻找通往宝藏的道路，穿越整个房间，并在路径上每一块可以通行的空地都要经过一次，最终找到宝藏。 房间的布局由一个 `grid` 表示，每个格子上可能是以下几种内容： - 数字 `1` 表示起点。 - 数字 `2` 表示宝藏所在的终点。 - 数字 `0` 表示可以通行的空地。 - 数字 `-1` 表示，无法通过。 在这次任务中，勇士们只能朝四个方向移动（上、下、左、右），且不能重复经过任何一块空地。你的任务是计算从起点到宝藏的所有，其中每一条路径必须经过每一块可以通行的空地。 输入：第一行包含两个整数 `m` 和 `n`，表示网格的行数和列数 `(1 <= m * n <= 20)`。 接下来的 `m` 行中，每行包含 `n` 个整数，表示房间的布局。每个整数的值可以是以下之一： - `1`：表示起点。 - `2`：表示终点。 - `0`：表示可以通行的空地。 - `-1`：表示障碍物。 输出：一个整数，表示从起点到终点的所有不同路径数目。如果不存在路径，输出 `0`。
这类题属于华为可信认证科目一方向中「DFS / 可信」方向的高频题型，通常考察对「DFS / 可信」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
输入的第一行包含两个整数 m 和 n，表示网格的行数和列数 (1 <= m * n <= 20)。
接下来的 m 行中，每行包含 n 个整数，表示房间的布局。每个整数的值可以是以下之一：
1：表示起点。2：表示终点。0：表示可以通行的空地。-1：表示障碍物。
输出描述
输出一个整数，表示从起点到终点的所有不同路径数目。如果不存在路径，输出 0。
示例
示例 1
输入示例
3 4 1 0 0 0 0 0 0 0 0 0 2 -1
输出示例
2
说明：
有以下两条路径：
(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2)(0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (2,2)
示例 2
输入示例
3 4 1 0 0 0 0 0 0 0 0 0 0 2
输出示例
4
说明：
有以下四条路径：
(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3)(0,0) -> (0,1) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (0,2) -> (0,3) -> (1,3) -> (2,3)(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3)(0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (2,2) -> (2,3)
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
