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. 代码实现
代码按上述思路构造：
vector<string>r(m);r[0].resize(n,'.');for(inti=1;i<m;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:vector<string>createGrid(intm,intn){vector<string>r(m);r[0].resize(n,'.');for(inti=1;i<m;i++){r[i].resize(n,'#');r[i][n-1]='.';}returnr;}};