2026-10-13：创建一个恰好有 K 条路径的网格图Ⅰ。用go语言，有 m、n、k 三个整数。请生成一个 m 行 n 列的字符矩阵，每个位置只能填“.
🤖 AI总结
主题
力扣3988题：构造恰好K条路径的网格图。
摘要
力扣3988题要求构造m×n矩阵使左上到右下恰好有k条路径，通过分支点构造法实现，附多语言代码。
关键信息
- 1 通过打通第一列和最后一行制造基础路径。
- 2 根据列数与k的关系在倒数第二行或第二列制造k个分支点。
- 3 提供Go、Python、C++三种语言的完整实现。
2026-10-13：创建一个恰好有 K 条路径的网格图Ⅰ。用go语言，有 m、n、k 三个整数。请生成一个 m 行 n 列的字符矩阵，每个位置只能填“.”或“。其中“.”表示可以经过的格子，“。所谓有效路线，是指从矩阵左上角出发，最终到达右下角，并且每一步只能向右或向下移动，同时途经的所有格子都必须是“.”。要求从左上角到右下角的有效路线数量恰好为 k。请输出任意一个满足条件的矩阵；如果不存在这样的矩阵，则输出空数组。
1 <= m, n <= 10。
1 <= k <= 4。
输入： m = 2, n = 3, k = 2。
输出： [“…”,”#..”]。
解释：
在这里插入图片描述
从 (0, 0) 到 (1, 2) 恰好有 k = 2 条有效路径：
(0, 0) → (0, 1) → (0, 2) → (1, 2)
(0, 0) → (0, 1) → (1, 1) → (1, 2)
题目来自力扣3988。
一、代码分步骤描述 1. 特判k == 4 && m == 3 && n == 3
如果输入恰好是m=3, n=3, k=4，代码直接返回一个预先写好的固定矩阵：
..#
...
#..这个矩阵恰好有 4 条从左上到右下的有效路径。
这是一个特殊情况，因为一般构造逻辑可能无法直接生成恰好 4 条路径的 3×3 网格，所以单独处理。
2. 处理只有一行或只有一列的情况
如果m == 1或者n == 1，也就是网格只有一行或者只有一列：
• 从左上角到右下角只有唯一一条路径，即一直向右或一直向下。
• 因此路径数量只能是 1。
• 如果k > 1，则不可能构造出恰好k条路径，直接返回空数组。
• 如果k == 1，则返回一个全部由.组成的网格。
3. 判断是否可能构造
如果m < k并且n < k，也就是行数和列数都小于k，代码认为无法构造出恰好k条路径，直接返回空数组。
这是因为后续的构造方法需要至少有k行或者至少有k列，才能通过打通一行或一列来制造k条路径。
4. 初始化全障碍网格
创建一个m行n列的二维字节数组，初始时所有格子都填#，表示全部是障碍物。
5. 打通第一列（除最后一行外）
对于前m-1行，也就是第0行到第m-2行，将第一列（列索引0）设置为.。
这样从左上角(0,0)开始，可以沿着第一列一直向下走到倒数第二行(m-2,0)。
注意最后一行暂时不处理，因为最后一行稍后会全部打通。
6. 打通最后一行
将最后一行，也就是第m-1行，全部设置为.。
这样从倒数第二行向下进入最后一行后，可以沿着最后一行一直向右走到右下角(m-1,n-1)。
此时网格的基本骨架是：
• 第一列从第 0 行到第 m-2 行都是.；
• 最后一行全部是.；
• 其他位置仍然是#。
7. 根据列数与k的关系制造恰好k条路径
接下来分两种情况：
情况 A：n >= k，即列数至少为k
将倒数第二行，也就是第m-2行，从第1列开始到第k-1列设置为.。
由于第0列之前已经设置为.，所以倒数第二行的前k列（第0列到第k-1列）全部都是.。
这样，从左上角沿第一列走到倒数第二行后，可以在倒数第二行向右移动。
在倒数第二行的前k个位置中的任意一个位置，都可以向下进入最后一行，然后沿最后一行向右到达终点。
因此恰好产生k条有效路径。
其他行除了第一列以外仍然是#，所以不会产生额外的路径。
情况 B：n < k，但根据前面的判断此时必有m >= k
将第二列（列索引1）从第m-k行到第m-2行设置为.。
注意最后一行已经是全.，所以实际上从第m-k行到第m-1行，第二列都是.。
这样，从左上角沿第一列向下走时，可以在第m-k行到第m-1行之间的任意一行向右进入第二列，然后继续向下走到最后一行，再向右到达终点。
一共有k行可以选择向右进入第二列，因此恰好产生k条有效路径。
其他行除了第一列和第二列被选中的位置外仍然是#，不会增加额外路径。
8. 转换为字符串数组返回
最后，将二维字节数组逐行转换为字符串，每一行一个字符串，组成字符串切片返回。
二、针对输入m = 2, n = 3, k = 2的实际执行过程
按照代码逻辑：
1. 不满足特判k == 4 && m == 3 && n == 3。
2.m != 1且n != 1。
3.m < k是2 < 2，为假；n < k是3 < 2，为假。所以不返回空数组。
4. 初始化2行3列全#：
###
###5. 前m-1 = 1行，即第0行，第一列设为.：
.##
###6. 最后一行全部设为.：
.##
...7. 因为n >= k（3 >= 2），所以设置倒数第二行（第0行）从第1列到第k-1 = 1列为.，即第0行第1列设为.：
..#
...8. 转换为字符串数组，返回：
["..#", "..."]这个矩阵中，从(0,0)到(1,2)的有效路径恰好有 2 条：
•(0,0) -> (0,1) -> (1,1) -> (1,2)
•(0,0) -> (1,0) -> (1,1) -> (1,2)
因此满足k = 2的条件。
题目示例给出的输出是["...", "#.."]，这也是一个合法答案，但代码实际生成的是["..#", "..."]。两者都满足恰好 2 条路径，题目要求返回任意一个即可。
三、时间复杂度分析
设网格大小为m行n列。
• 特判：常数时间O(1)。
• 处理一行或一列：需要生成m个长度为n的字符串，时间复杂度O(m * n)。
• 初始化二维数组并全部填#：需要访问m * n个格子，时间复杂度O(m * n)。
• 打通第一列：循环m-1次，时间复杂度O(m)。
• 打通最后一行：循环n次，时间复杂度O(n)。
• 根据n与k的关系设置额外格子：循环次数最多为k-1，而k <= 4，所以是常数时间O(1)。
• 最后将二维数组转换为字符串数组：需要遍历m行，每行长度n，时间复杂度O(m * n)。
因此总时间复杂度为：
O(m * n)由于题目中m, n <= 10，实际运行非常快。
四、额外空间复杂度分析
• 主要额外空间是二维字节数组a，大小为m行n列，占用O(m * n)空间。
• 返回的字符串数组也需要O(m * n)空间来存储结果。
• 其他变量如循环索引、临时变量等均为常数级。
因此总额外空间复杂度为：
O(m * n)五、总结
该函数通过“打通第一列 + 打通最后一行 + 在倒数第二行或第二列制造k个分支点”的方式，构造出恰好k条有效路径的网格。
对于无法构造的情况（单行单列且k > 1，或者行列数都小于k），返回空数组。
整体时间复杂度和额外空间复杂度都是O(m * n)，在题目约束下非常高效。
Go完整代码如下：
package main
import (
"bytes"
"fmt"
"strings"
)
func createGrid(m, n, k int) []string {
// 特判
if k == 4 && m == 3 && n == 3 {
return []string{"..#", "...", "#.."}
}
if m == 1 || n == 1 {
// 一行或一列，只能有一种方案
if k > 1 {
returnnil
}
// 全为 '.'
ans := make([]string, m)
row := strings.Repeat(".", n)
for i := range ans {
ans[i] = row
}
return ans
}
// 至少要有 k 行或 k 列（特殊情况上面已判断）
if m < k && n < k {
returnnil
}
// 初始全为 '#'
a := make([][]byte, m)
for i := range m - 1 {
a[i] = bytes.Repeat([]byte{'#'}, n)
a[i][0] = '.'// 第一列全为 '.'
}
a[m-1] = bytes.Repeat([]byte{'.'}, n) // 最后一行全为 '.'
if n >= k { // 至少有 k 列
// 倒数第二行开头 k 个 '.'
for j := 1; j < k; j++ {
a[m-2][j] = '.'
}
} else { // 至少有 k 行
// 第二列末尾 k 个 '.'
for _, row := range a[m-k : m-1] {
row[1] = '.'
}
}
ans := make([]string, m)
for i, row := range a {
ans[i] = string(row)
}
return ans
}func main() {
m := 2
n := 3
k := 2
result := createGrid(m, n, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def createGrid(m, n, k):
# 特判
if k == 4 and m == 3 and n == 3:
return ["..#", "...", "#.."]
if m == 1 or n == 1:
# 一行或一列，只能有一种方案
if k > 1:
return []
# 全为 '.'
row = "." * n
return [row for _ in range(m)]
# 至少要有 k 行或 k 列（特殊情况上面已判断）
if m < k and n < k:
return []
# 初始全为 '#'
a = []
for i in range(m - 1):
row = ['#'] * n
row[0] = '.' # 第一列全为 '.'
a.append(row)
a.append(['.'] * n) # 最后一行全为 '.'
if n >= k: # 至少有 k 列
# 倒数第二行开头 k 个 '.'
for j in range(1, k):
a[m - 2][j] = '.'
else: # 至少有 k 行
# 第二列末尾 k 个 '.'
for row in a[m - k:m - 1]:
row[1] = '.'
return [''.join(row) for row in a]if __name__ == "__main__":
m = 2
n = 3
k = 2
result = createGrid(m, n, k)
print(result)
C++完整代码如下：
using namespace std;
vector createGrid(int m, int n, int k) {
// 特判
if (k == 4 && m == 3 && n == 3) {
return {"..#", "...", "#.."};
}
if (m == 1 || n == 1) {
// 一行或一列，只能有一种方案
if (k > 1) {
return {};
}
string row(n, '.');
return vector(m, row);
}
// 至少要有 k 行或 k 列（特殊情况上面已判断）
if (m < k && n < k) {
return {};
}
// 初始全为 '#'
vector > a(m, vector (n, '#'));
// 第一列（除最后一行外）设为 '.'
for (int i = 0; i < m - 1; ++i) {
a[i][0] = '.';
}
// 最后一行全部设为 '.'
for (int j = 0; j < n; ++j) {
a[m - 1][j] = '.';
}
if (n >= k) { // 至少有 k 列
// 倒数第二行开头 k 个 '.'
for (int j = 1; j < k; ++j) {
a[m - 2][j] = '.';
}
} else { // 至少有 k 行
// 第二列末尾 k 个 '.'
for (int i = m - k; i < m - 1; ++i) {
a[i][1] = '.';
}
}
vector ans;
for (int i = 0; i < m; ++i) {
ans.push_back(string(a[i].begin(), a[i].end()));
}
return ans;
}int main() {
int m = 2, n = 3, k = 2;
vector result = createGrid(m, n, k);
for (conststring& row : result) {
cout << row << endl;
}
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
