2026-10-13：创建一个恰好有 K 条路径的网格图Ⅰ。用go语言，有 m、n、k 三个整数。请生成一个 m 行 n 列的字符矩阵，每个位置只能填“.

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 条路径的 3x3 网格，所以单独处理。

2. 处理只有一行或只有一列的情况

如果m == 1或者n == 1，也就是网格只有一行或者只有一列：

• • 从左上角到右下角只有唯一一条路径，即一直向右或一直向下。

• • 因此路径数量只能是 1。

• • 如果k > 1，则不可能构造出恰好k条路径，直接返回空数组。

• • 如果k == 1，则返回一个全部由.组成的网格。

如果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 行都是.；

• • 最后一行全部是.；

• • 其他位置仍然是#。

接下来分两种情况：

情况 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. 1. 不满足特判k == 4 && m == 3 && n == 3。

2. 2.m != 1且n != 1。

3. 3.m < k是2 < 2，为假；n < k是3 < 2，为假。所以不返回空数组。

4. 4. 初始化2行3列全#：

   ###
   ###

5. 5. 前m-1 = 1行，即第0行，第一列设为.：

   .##
   ###

6. 6. 最后一行全部设为.：

   .##
   ...

7. 7. 因为n >= k（3 >= 2），所以设置倒数第二行（第0行）从第1列到第k-1 = 1列为.，即第0行第1列设为.：

   ..#
   ...

8. 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助力您的未来发展。