DiffPush Tier Recursion · Try Out All Combos O(3^(n^2)) worst case — each open bay branches to at most three new directions · O(n^2) recursion depth and visited marking
A cleaning robot starts in the top-left bay of a square warehouse and must reach the bottom-right bay, where some bays are walled off. The robot may step up, down, left, or right into open bays, never visiting a bay twice on one route. Route control wants the complete catalogue of possible sweeps, each written as the sequence of moves taken.
Input: An n x n binary matrix m (1 = open bay, 0 = blocked) and its size n.
Output: Every path string of moves (U/D/L/R) from (0,0) to (n-1,n-1), sorted lexicographically by the verifier.
2 <= n <= 10m[0][0] = 1 and m[n-1][n-1] = 1 for solvable gridsInput: {"n":4,"m":[[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]}
Output: ["DDRDRR","DRDDRR"]
Exactly two sweeps exist: one cutting right early, one running down first.
Input: {"n":2,"m":[[1,1],[1,1]]}
Output: ["DR","RD"]
A fully open 2x2 admits the two obvious two-step routes.