企业官网建设流程全解析

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，则返回一个全部由.组成的网格。

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完整代码如下：

packagemainimport("bytes""fmt""strings")funccreateGrid(m,n,kint)[]string{// 特判ifk==4&&m==3&&n==3{return[]string{"..#","...","#.."}}ifm==1||n==1{// 一行或一列，只能有一种方案ifk>1{returnnil}// 全为 '.'ans:=make([]string,m)row:=strings.Repeat(".",n)fori:=rangeans{ans[i]=row}returnans}// 至少要有 k 行或 k 列（特殊情况上面已判断）ifm<k&&n<k{returnnil}// 初始全为 '#'a:=make([][]byte,m)fori:=rangem-1{a[i]=bytes.Repeat([]byte{'#'},n)a[i][0]='.'// 第一列全为 '.'}a[m-1]=bytes.Repeat([]byte{'.'},n)// 最后一行全为 '.'ifn>=k{// 至少有 k 列// 倒数第二行开头 k 个 '.'forj:=1;j<k;j++{a[m-2][j]='.'}}else{// 至少有 k 行// 第二列末尾 k 个 '.'for_,row:=rangea[m-k:m-1]{row[1]='.'}}ans:=make([]string,m)fori,row:=rangea{ans[i]=string(row)}returnans}funcmain(){m:=2n:=3k:=2result:=createGrid(m,n,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defcreateGrid(m,n,k):# 特判ifk==4andm==3andn==3:return["..#","...","#.."]ifm==1orn==1:# 一行或一列，只能有一种方案ifk>1:return[]# 全为 '.'row="."*nreturn[rowfor_inrange(m)]# 至少要有 k 行或 k 列（特殊情况上面已判断）ifm<kandn<k:return[]# 初始全为 '#'a=[]foriinrange(m-1):row=['#']*n row[0]='.'# 第一列全为 '.'a.append(row)a.append(['.']*n)# 最后一行全为 '.'ifn>=k:# 至少有 k 列# 倒数第二行开头 k 个 '.'forjinrange(1,k):a[m-2][j]='.'else:# 至少有 k 行# 第二列末尾 k 个 '.'forrowina[m-k:m-1]:row[1]='.'return[''.join(row)forrowina]if__name__=="__main__":m=2n=3k=2result=createGrid(m,n,k)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<string>usingnamespacestd;vector<string>createGrid(intm,intn,intk){// 特判if(k==4&&m==3&&n==3){return{"..#","...","#.."};}if(m==1||n==1){// 一行或一列，只能有一种方案if(k>1){return{};}stringrow(n,'.');returnvector<string>(m,row);}// 至少要有 k 行或 k 列（特殊情况上面已判断）if(m<k&&n<k){return{};}// 初始全为 '#'vector<vector<char>>a(m,vector<char>(n,'#'));// 第一列（除最后一行外）设为 '.'for(inti=0;i<m-1;++i){a[i][0]='.';}// 最后一行全部设为 '.'for(intj=0;j<n;++j){a[m-1][j]='.';}if(n>=k){// 至少有 k 列// 倒数第二行开头 k 个 '.'for(intj=1;j<k;++j){a[m-2][j]='.';}}else{// 至少有 k 行// 第二列末尾 k 个 '.'for(inti=m-k;i<m-1;++i){a[i][1]='.';}}vector<string>ans;for(inti=0;i<m;++i){ans.push_back(string(a[i].begin(),a[i].end()));}returnans;}intmain(){intm=2,n=3,k=2;vector<string>result=createGrid(m,n,k);for(conststring&row:result){cout<<row<<endl;}return0;}