Full Sweep Routes

HardBacktracking

Problem

A cleaning robot works on a grid grid where 1 is its start cell, 2 is the docking cell, 0 is a floor cell and -1 is an obstacle. There is exactly one start and one dock.

The robot moves up, down, left or right. Count the routes from the start to the dock that visit every non-obstacle cell exactly once (start and dock included).

Example 1

Input:
grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]]
Output:
2

Both routes snake through all 11 open cells before docking.

Example 2

Input:
grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2]]
Output:
4

Constraints

  • 1 ≤ rows · cols ≤ 20
  • grid[i][j] is -1, 0, 1 or 2.
  • Exactly one cell is 1 and exactly one is 2.

Hint

Show the first hint

You need to know, when you reach the dock, whether every open cell was used. What should you count up front?

Walkthrough

How to approach it

01Clarify before coding

  • Must the robot visit every open cell? Yes, exactly once.
  • Can it pass through the dock and come back? No, reaching the dock ends the route.
  • Grid size? At most 20 cells, which is what makes exhaustive search acceptable.

02Brute force

Generate every ordering of the open cells and check that consecutive cells are adjacent and that it starts at 1 and ends at 2.

Cost: O(k!) orderings for k open cells: 18! ≈ 6.4 · 10^15.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.