Skip to content
Onsite
26 / 26

Return to Origin in a Maze

HardP3Coding

grid is a maze given as strings of '.' (open cell) and '*' (blocked cell). You stand at the open cell (r, c) (0-based row and column). A move goes one cell up, down, left or right into an open cell.

Return true if you can walk a closed loop that ends back at (r, c), makes at least k moves in total, and never enters any other cell more than once. Only the final move may land on the start cell. A loop in a grid always has at least 4 moves, so a loop of 2 moves (stepping out and straight back) is not allowed.

Example 1

Input
grid = ["..",".."], r = 0, c = 0, k = 4
Output
true
Why
The only loop is the 2 x 2 square, with 4 moves.

Example 2

Input
grid = ["..",".."], r = 0, c = 0, k = 5
Output
false
Why
A 2 x 2 grid has only the 4-move loop.

Example 3

Input
grid = ["...","...","..."], r = 1, c = 1, k = 4
Output
true

Constraints

  • 1 <= rows, columns <= 5
  • 0 <= k <= 30
  • (r, c) is inside the grid; if it is a '*' cell, the answer is false.

Hints

Run checks the 3 visible tests, Submit all 16.