Skip to content

3990. Create Grid With Exactly K Paths II πŸ”’

Description

You are given an integer k.

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

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

The grid must contain at most 25 rows and at most 25 columns.

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), where m and n are the dimensions of your constructed grid.
  • 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 are exactly k valid paths from the top-left cell to the bottom-right cell. If no such grid exists, return an empty array.

Β 

Example 1:

Input: k = 2

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

Explanation:

The grid contains exactly 2 valid paths from (0, 0) to (2, 2):

  • (0, 0) β†’ (0, 1) β†’ (1, 1) β†’ (1, 2) β†’ (2, 2)
  • (0, 0) β†’ (0, 1) β†’ (1, 1) β†’ (2, 1) β†’ (2, 2)

Example 2:

Input: k = 3

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

Explanation:

​​​​​​​

The grid contains exactly 3 valid paths from (0, 0) to (2, 2):

  • (0, 0) β†’ (0, 1) β†’ (0, 2) β†’ (1, 2) β†’ (2, 2)
  • (0, 0) β†’ (0, 1) β†’ (1, 1) β†’ (1, 2) β†’ (2, 2)
  • (0, 0) β†’ (0, 1) β†’ (1, 1) β†’ (2, 1) β†’ (2, 2)

Β 

Constraints:​​​​​​​

  • 1 <= k <= 1000

Solutions

Solution 1

1


1


1


1

Comments