3990. 创建一个恰好有 K 条路径的网格图 II 🔒
题目描述
给定一个整数 k。
构建一个仅由字符 '.' 和 '#' 组成的网格，其中：
'.'表示一个空闲单元格。'#'表示一个障碍单元格。
网格 最多 包含 25 行和 25 列。
有效路径 是一系列空闲单元格，满足：
- 从左上角单元格
(0, 0)开始。 - 终点位于右下角单元格
(m - 1, n - 1)，其中m和n是你构建的网格的尺寸。 - 移动方式只允许：
- 向右, 从
(i, j)到(i, j + 1)，或 - 向下，从
(i, j)到(i + 1, j)。
- 向右, 从
返回任意一个网格，使得从左上角单元格到右下角单元格 恰好有 k 条有效路径。如果不存在这样的网格，则返回一个空数组。
示例 1：
输入：k = 2
输出：["..#","#..","#.."]
解释：
网格中恰好有两条从 (0, 0) 到 (2, 2) 的有效路径：
(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2)(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
示例 2：
输入：k = 3
输出：["...","#..","#.."]
解释：
网格中恰好有 3 条从 (0, 0) 到 (2, 2) 的有效路径：
(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2)(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2)(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
提示：
1 <= k <= 1000
解法
方法一
思考
与 I 相同，但尺寸自选且至多 \(25\times 25\)，只需对某个足够大的网格嵌入 \(k\) 条路径。可用「一条主干加若干长度为 \(t\) 的旁路」把 \(k\) 写成二进制或斐波那契和。
\(k\le 1000\)，在 \(25\) 格的预算内足够放置这些旁路。仓库中该题尚无实现代码，思考止于「自选尺寸下把 \(k\) 拆成可构造的路径块」。
1 | |
1 | |
1 | |
1 | |