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
解法
方法一
1 | |
1 | |
1 | |
1 | |