Skip to content

3963. Create Grid With Exactly One Path

Description

You are given two integers m and n, representing the number of rows and columns of a grid.

Construct any m x n grid consisting only of the characters '.' and '#', where:

  • '.' represents a free cell.
  • '#' represents an obstacle cell.

A valid path is a sequence of free cells that:

  • Starts at the top-left cell (0, 0).
  • Ends at the bottom-right cell (m - 1, n - 1).
  • Moves only:
    • Right, from (i, j) to (i, j + 1), or
    • Down, from (i, j) to (i + 1, j).

Return any grid such that there is exactly one valid path from the top-left cell to the bottom-right cell.

 

Example 1:

Input: m = 2, n = 3

Output: ["..#","#.."]

Explanation:

The only valid path is: (0,0) → (0,1) → (1,1) → (1,2)

Example 2:

Input: m = 3, n = 3

Output: ["..#","#..","##."]

Explanation:

The only valid path is: (0,0) → (0,1) → (1,1) → (1,2) → (2,2)

Example 3:

Input: m = 1, n = 4

Output: ["...."]

Explanation:

The only valid path is: (0,0) → (0,1) → (0,2) → (0,3)

 

Constraints:

  • 1 <= m, n <= 25

Solutions

Solution 1: Construction

Thinking

We only need exactly one down/right path from the top-left to the bottom-right. Fill the grid with walls, then open the first row and the last column, leaving the unique polyline “across the top, then down the right”.

\(m,n\le 25\), so construction is linear in the grid size.

We construct the grid as follows:

  • First, construct a grid filled entirely with #.
  • Set all elements in the first row to ..
  • Set all elements in the last column to ..
  • Return the constructed grid.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the number of rows and columns in the grid, respectively.

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(''));
}

Comments