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如果输入恰好是m3, n3, k4代码直接返回一个预先写好的固定矩阵..# ... #..这个矩阵恰好有 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条路径接下来分两种情况情况 An k即列数至少为k将倒数第二行也就是第m-2行从第1列开始到第k-1列设置为.。由于第0列之前已经设置为.所以倒数第二行的前k列第0列到第k-1列全部都是.。这样从左上角沿第一列走到倒数第二行后可以在倒数第二行向右移动。在倒数第二行的前k个位置中的任意一个位置都可以向下进入最后一行然后沿最后一行向右到达终点。因此恰好产生k条有效路径。其他行除了第一列以外仍然是#所以不会产生额外的路径。情况 Bn 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的实际执行过程按照代码逻辑不满足特判k 4 m 3 n 3。m ! 1且n ! 1。m k是2 2为假n k是3 2为假。所以不返回空数组。初始化2行3列全#### ###前m-1 1行即第0行第一列设为..## ###最后一行全部设为..## ...因为n k3 2所以设置倒数第二行第0行从第1列到第k-1 1列为.即第0行第1列设为...# ...转换为字符串数组返回[..#, ...]这个矩阵中从(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(bytesfmtstrings)funccreateGrid(m,n,kint)[]string{// 特判ifk4m3n3{return[]string{..#,...,#..}}ifm1||n1{// 一行或一列只能有一种方案ifk1{returnnil}// 全为 .ans:make([]string,m)row:strings.Repeat(.,n)fori:rangeans{ans[i]row}returnans}// 至少要有 k 行或 k 列特殊情况上面已判断ifmknk{returnnil}// 初始全为 #a:make([][]byte,m)fori:rangem-1{a[i]bytes.Repeat([]byte{#},n)a[i][0].// 第一列全为 .}a[m-1]bytes.Repeat([]byte{.},n)// 最后一行全为 .ifnk{// 至少有 k 列// 倒数第二行开头 k 个 .forj:1;jk;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):# 特判ifk4andm3andn3:return[..#,...,#..]ifm1orn1:# 一行或一列只能有一种方案ifk1:return[]# 全为 .row.*nreturn[rowfor_inrange(m)]# 至少要有 k 行或 k 列特殊情况上面已判断ifmkandnk:return[]# 初始全为 #a[]foriinrange(m-1):row[#]*n row[0].# 第一列全为 .a.append(row)a.append([.]*n)# 最后一行全为 .ifnk:# 至少有 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__:m2n3k2resultcreateGrid(m,n,k)print(result)C完整代码如下#includeiostream#includevector#includestringusingnamespacestd;vectorstringcreateGrid(intm,intn,intk){// 特判if(k4m3n3){return{..#,...,#..};}if(m1||n1){// 一行或一列只能有一种方案if(k1){return{};}stringrow(n,.);returnvectorstring(m,row);}// 至少要有 k 行或 k 列特殊情况上面已判断if(mknk){return{};}// 初始全为 #vectorvectorchara(m,vectorchar(n,#));// 第一列除最后一行外设为 .for(inti0;im-1;i){a[i][0].;}// 最后一行全部设为 .for(intj0;jn;j){a[m-1][j].;}if(nk){// 至少有 k 列// 倒数第二行开头 k 个 .for(intj1;jk;j){a[m-2][j].;}}else{// 至少有 k 行// 第二列末尾 k 个 .for(intim-k;im-1;i){a[i][1].;}}vectorstringans;for(inti0;im;i){ans.push_back(string(a[i].begin(),a[i].end()));}returnans;}intmain(){intm2,n3,k2;vectorstringresultcreateGrid(m,n,k);for(conststringrow:result){coutrowendl;}return0;}