0993HardArrayBacktrackingBit ManipulationMatrixHamiltonian Path

Sweeping Every Open Bay Once

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def unique_paths_i_i_i(floor: list[list[int]]) -> int:

Java

public int uniquePathsIII(int[][] floor)

The intended approach

Time O(3^k) loosely for k bays, since after the first step each move has at most three ways on that are not straight back where it came from.Space O(k) for the depth of the walk.

With no more than twenty bays on the floor there are few enough sweeps to walk out in full, so long as the walk never wanders over ground it has already covered. Scan the grid once for the starting bay, the finishing bay, and how many bays have to be stood on altogether, which is every bay that is not blocked. Then step out from the starting bay, marking each bay as taken on the way in and releasing it again on the way back out, so each partial sweep is tried without ever standing twice on the same bay. On arriving at the finishing bay, stop and count the sweep only when the tally of bays stood on matches the tally that had to be covered; arriving early means some bay was missed. Holding the taken bays as the bits of one whole number, a bit per bay, turns marking and releasing into a pair of cheap flips and keeps nothing but that number and a tally on the stack. The walk never goes deeper than the number of bays.

Pythonentry point: unique_paths_i_i_i

def unique_paths_i_i_i(floor):
    rows = len(floor)
    cols = len(floor[0])
    need = 0
    start = 0
    finish = 0
    for r in range(rows):
        for c in range(cols):
            mark = floor[r][c]
            if mark != -1:
                need += 1
            if mark == 1:
                start = r * cols + c
            elif mark == 2:
                finish = r * cols + c
    total = 0
    def walk(at, taken, count):
        nonlocal total
        if at == finish:
            if count == need:
                total += 1
            return
        r = at // cols
        c = at % cols
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue
            if floor[nr][nc] == -1:
                continue
            spot = nr * cols + nc
            if taken >> spot & 1:
                continue
            walk(spot, taken | 1 << spot, count + 1)
    walk(start, 1 << start, 1)
    return total

The obvious version

Gather the bays that are not blocked into one collection, then push partial sweeps onto a stack, each carrying where it stands and the whole set of bays it has stood on. Popping a sweep that stands on the finishing bay, count it only when its set of bays matches the collection outright. Compares whole sets of bays and keeps every partial sweep on a stack, rather than counting bays and flipping bits on the way in and out.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_unique_paths_i_i_i(floor):
    rows = len(floor)
    cols = len(floor[0])
    open_bays = set()
    start = None
    finish = None
    for r in range(rows):
        for c in range(cols):
            mark = floor[r][c]
            if mark != -1:
                open_bays.add((r, c))
            if mark == 1:
                start = (r, c)
            elif mark == 2:
                finish = (r, c)
    open_bays = frozenset(open_bays)
    total = 0
    stack = [(start, frozenset([start]))]
    while stack:
        here, seen = stack.pop()
        if here == finish:
            if seen == open_bays:
                total += 1
            continue
        r, c = here
        for there in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if there in open_bays and there not in seen:
                stack.append((there, seen | frozenset([there])))
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in