跳转至

3963. 构造恰好一条路径的网格

题目描述

给你两个整数 m 和 n，分别表示网格的行数和列数。

请你构造 任意 一个只包含字符 '.' 和 '#' 的 m x n 网格，其中：

  • '.' 表示空单元格。
  • '#' 表示障碍物单元格。

有效路径 是满足以下条件的空单元格序列：

  • 从左上角单元格 (0, 0) 开始。
  • 在右下角单元格 (m - 1, n - 1) 结束。
  • 只能向：
    • 右移动，从 (i, j) 到 (i, j + 1)，或者
    • 下移动，从 (i, j) 到 (i + 1, j)。

返回任意一个从左上角到右下角 恰好只有一条有效路径 的网格。

 

示例 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

解法

方法一：构造

我们按照如下方式构造网格：

  • 先构造一个全为 # 的网格。
  • 将第一行的所有元素都设置为 .。
  • 将最后一列的所有元素都设置为 .。
  • 返回构造好的网格。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别是网格的行数和列数。

1
2
3
4
5
6
7
class Solution:
    def createGrid(self, m: int, n: int) -> list[str]:
        g = [["#"] * n for _ in range(m)]
        g[0] = ["."] * n
        for i in range(m):
            g[i][-1] = "."
        return ["".join(row) for row in g]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String[] createGrid(int m, int n) {
        char[][] g = new char[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(g[i], '#');
        }

        Arrays.fill(g[0], '.');

        for (int i = 0; i < m; i++) {
            g[i][n - 1] = '.';
        }

        String[] ans = new String[m];
        for (int i = 0; i < m; i++) {
            ans[i] = new String(g[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<string> createGrid(int m, int n) {
        vector<string> g(m, string(n, '#'));

        g[0] = string(n, '.');

        for (int i = 0; i < m; i++) {
            g[i][n - 1] = '.';
        }

        return g;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func createGrid(m int, n int) []string {
    g := make([][]byte, m)
    for i := range g {
        g[i] = make([]byte, n)
        for j := range g[i] {
            g[i][j] = '#'
        }
    }

    for j := 0; j < n; j++ {
        g[0][j] = '.'
    }

    for i := 0; i < m; i++ {
        g[i][n-1] = '.'
    }

    ans := make([]string, m)
    for i := range g {
        ans[i] = string(g[i])
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function createGrid(m: number, n: number): string[] {
    const g: string[][] = Array.from({ length: m }, () => Array(n).fill('#'));

    g[0].fill('.');

    for (let i = 0; i < m; i++) {
        g[i][n - 1] = '.';
    }

    return g.map(row => row.join(''));
}

评论