3963. 构造恰好一条路径的网格网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你两个整数m和n分别表示网格的行数和列数。请你构造任意一个只包含字符.和#的m x n网格其中.表示空单元格。#表示障碍物单元格。有效路径是满足以下条件的空单元格序列从左上角单元格(0, 0)开始。在右下角单元格(m - 1, n - 1)结束。只能向右移动从(i, j)到(i, j 1)或者下移动从(i, j)到(i 1, j)。返回任意一个从左上角到右下角恰好只有一条有效路径的网格。输入描述两个整数m和n分别表示网格的行数和列数。输出描述返回一个m x n的字符串数组每个字符串仅由.和#组成表示满足「从左上角到右下角恰好只有一条有效路径」的网格。多解时返回任意一个均可。示例 1输入m 2, n 3输出[. .#,#..]写作网格形式. . # # . .解释唯一的有效路径是(0,0) - (0,1) - (1,1) - (1,2)示例 2输入m 3, n 3输出[. .#,#..,##.]写作网格形式. . # # . . # # .解释唯一的有效路径是(0,0) - (0,1) - (1,1) - (1,2) - (2,2)示例 3输入m 1, n 4输出[....]解释唯一的有效路径是(0,0) - (0,1) - (0,2) - (0,3)数据范围1 ≤ m , n ≤ 25 1 \le m, n \le 251≤m,n≤25解题思路本题是构造性贪心问题。题目不要求唯一答案只需构造一个m × n的网格使得从左上角(0,0)到右下角(m-1,n-1)、只能向右或向下走的有效路径恰好只有一条。1. 构造目标我们希望把整张网格设计成一条“唯一通道”第一行全部为.允许从左上角一直向右走从第二行开始每行只保留最后一列为.其余位置全部设为#这样从第一行最右端开始只能沿着最后一列一路向下走到右下角。换句话说构造出的唯一路径是( 0 , 0 ) → ( 0 , 1 ) → ⋯ → ( 0 , n − 1 ) → ( 1 , n − 1 ) → ⋯ → ( m − 1 , n − 1 ) (0,0)\to(0,1)\to\cdots\to(0,n-1)\to(1,n-1)\to\cdots\to(m-1,n-1)(0,0)→(0,1)→⋯→(0,n−1)→(1,n−1)→⋯→(m−1,n−1)这条路径先沿着第一行向右走到底再沿着最后一列向下走到底。2. 为什么路径唯一考虑任意一条从(0,0)到(m-1,n-1)的合法路径。只要路径还在第一行它只能向右走因为第二行从第0列到第n-2列全部是障碍物#无法向下进入因此路径必须一直走到(0,n-1)到达最后一列后由于第一行以下只有最后一列是空地路径只能不断向下最终到达(m-1,n-1)。中间没有任何分叉口所以有效路径恰好只有一条。3. 代码实现代码按上述思路构造vectorstringr(m);r[0].resize(n,.);for(inti1;im;i){r[i].resize(n,#);r[i][n-1].;}具体来说r[0].resize(n, .)第一行全部填.对于第1行到第m-1行r[i].resize(n, #)整行先填#r[i][n - 1] .只把最后一列改成空地.。这样得到的网格形如. . . ... . # # # ... . # # # ... . ... # # # ... .其中第一行全为空地最后一列全为空地其余位置都是障碍物。4. 边界情况当m 1时只有第一行整行都是.路径只能一路向右恰好唯一当n 1时第一行只有一个.其余每行也只有最后一列是.路径只能一路向下恰好唯一当m n 1时网格为单个.路径长度为 0也恰好唯一。这些情况代码都能自然处理。5. 复杂度分析构造网格需要填充m × n个字符时间复杂度为O ( m n ) O(mn)O(mn)返回结果本身需要O ( m n ) O(mn)O(mn)空间因此空间复杂度为O ( m n ) O(mn)O(mn)。总结把第一行全部设为空地把最后一列从第二行开始全部设为空地其余位置全部设为障碍物。这样从左上角出发只能先沿第一行走到最右端再沿最后一列向下走到右下角形成唯一一条有效路径。构造简单且天然满足题目要求。代码内容classSolution{public:vectorstringcreateGrid(intm,intn){vectorstringr(m);r[0].resize(n,.);for(inti1;im;i){r[i].resize(n,#);r[i][n-1].;}returnr;}};