Show problems as
Classic problem #980HardArrayBacktrackingBit ManipulationMatrixHamiltonian Path

Unique Paths III

Real-world version: Sweeping Every Open Bay Once
Tracked in this browser only
Read Unique Paths III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCounting Problems · Dynamic Programming, animated step by step

A warehouse floor is given as the grid floor, where each cell carries one of four markings:

  • 1 marks the single starting bay,
  • 2 marks the single finishing bay,
  • 0 marks an open bay that has to be swept,
  • -1 marks a blocked bay that cannot be entered.

A sweep begins on the starting bay and ends on the finishing bay, moving each time to a bay that shares an edge with the current one. It has to cover every open bay, and no bay may be stood on more than once. The starting and finishing bays are not open bays, and each of them is stood on exactly once, as the two ends of the sweep.

Return how many different sweeps the floor allows. Two sweeps differ when the order of bays they stand on differs.

Examples

Example 1

Input
floor = [[1, 0, 0], [0, 0, 0], [0, 0, 2]]
Output
2

Every bay is open, so all nine have to be stood on with the last one being the far corner. Going down the left column, one step right, up the middle column, one step right, then down the right column is one way. Going along the top row, one step down, back along the middle row, one step down, then along the bottom row is the other. Nothing else covers the floor.

Example 2

Input
floor = [[1, 0], [0, 2]]
Output
0

All four bays have to be stood on, which takes three steps from the starting bay. Three steps around a square of four bays always end up next door to where they began, never diagonally across, so no sweep works.

Example 3

Input
floor = [[1, -1], [0, 2]]
Output
1

The blocked bay leaves one route: down, then across.

Constraints

  • 1 <= floor.length <= 20
  • 1 <= floor[i].length <= 20
  • The grid holds at most 20 bays in all.
  • -1 <= floor[i][j] <= 2
  • There is exactly one starting bay and exactly one finishing bay.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def unique_paths_i_i_i(floor: list[list[int]]) -> int:
Java
public int uniquePathsIII(int[][] floor)

More on the same topics