3963. Create Grid With Exactly One Path

1. Description

Given integers m and n, construct an m x n grid using ‘.’ for free cells and ‘#’ for obstacles.
A valid path starts at (0,0), ends at (m - 1,n - 1), visits only free cells, and moves one cell right or down at each step.
Return any grid with exactly one valid path between these two corners.

2. Example

Example 1

Input: m = 2, n = 3
Output: ["..#","#.."]
Explanation: There is a single route: (0,0) → (0,1) → (1,1) → (1,2).

Example 2

Input: m = 3, n = 3
Output: ["..#","#..","##."]
Explanation: The only route is (0,0) → (0,1) → (1,1) → (1,2) → (2,2).

Example 3

Input: m = 1, n = 4
Output: ["...."]
Explanation: The path follows the single row from (0,0) through (0,3).

3. Constraints

• 1 <= m, n <= 25

4. Solutions

Construction

m = number of rows, n = number of columns
Time complexity: O(mn)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<string> createGrid(int m, int n) {
        vector<string> grid(m, string(n, '#'));
        grid.front() = string(n, '.');
        for (int i = 1; i < m; ++i) {
            grid[i].back() = '.';
        }

        return grid;
    }
};