L19. Rat in A Maze | Backtracking

Main ideas / lesson conveyed

• “Rat in a Maze” problem definition

  • A rat starts at the top-left cell (0,0) in an n×n square matrix.
  • The rat’s goal is to reach the bottom-right cell (n−1, n−1).
  • The rat must find all possible paths from start to destination.

• Movement rules

  • The rat can move in four directions: Up, Down, Left, Right.
  • A move into a cell is allowed only if the target cell value is 1.
  • Cells with value 0 are blocked.

• No revisiting rule (backtracking requirement)

  • Within a single path, the rat cannot visit any cell more than once.
  • Therefore, the algorithm uses a visited matrix/array to prevent cycles and infinite loops.

• Output requirement

  • All valid paths must be printed in lexicographical order (dictionary order).
  • Paths are represented as strings of direction letters (e.g., "ddr").
  • To achieve lexicographical ordering, the exploration order is chosen as:
    • Down, Left, Right, Up

Methodology / algorithm described (with backtracking + recursion)

Core approach: recursive DFS with backtracking

• Start recursion at (0,0) with:

  • an initially empty move string
  • a visited matrix initialized to false

• At each recursive call for position (i, j):

  • If (i, j) == (n−1, n−1):
    • store the current move string as one valid path
    • return
  • Otherwise, try all valid moves in lexicographic direction order:
    • Down
    • Left
    • Right
    • Up

For each attempted move

• Check boundaries (the new position must be inside the matrix).
• Check visited (must not have been visited already in this path).
• Check cell value (must be 1).
• If valid:
  • mark the new cell as visited
  • append the corresponding move letter to the path string:
    • D, L, R, U
  • recurse to the new cell
  • after returning, backtrack:
    • unmark the cell as visited
    • the move is effectively removed by returning from recursion

Example path construction (illustrative)

• The video discusses constructing paths via exploration such as:
  • DDDRDRR-style exploration
• Destination-reaching examples mentioned include:
  • DDRD RR (also described as DDRD R R with spacing in narration)
  • DRDRR
• The key takeaway is that the chosen direction try-order (D first, then L/R, then U) is what naturally produces lexicographical order in the generated outputs.

Optimization: reduce multiple direction conditionals

• Instead of separate conditionals for each direction, use direction arrays:
  • di and dj represent row/column changes for moves
• Iterate through directions in the desired order:
  • down, left, right, up
• For each direction index k:
  • compute next position:
    • ni = i + di[k]
    • nj = j + dj[k]
  • perform combined checks:
    • 0 <= ni < n
    • 0 <= nj < n
    • visited[ni][nj] == false
    • matrix[ni][nj] == 1
  • then proceed with the same mark → recurse → unmark backtracking flow

Time/space complexity explained

• Time complexity (approximation given)

  • Up to an approximate form like 4^(n*m / ?)
  • Rationale: from each cell, up to four moves are attempted (subject to boundaries and 0 blocks).

• Space complexity

  • Auxiliary recursion depth (worst case): described as roughly proportional to n² (via narrative suggesting worst-case path length)
  • Plus the visited structure: n × n

Speakers / sources featured

• Primary speaker: The video’s host/instructor (name not provided in subtitles)
• Promotional source: Coding Ninjas (training platform/company; mentioned as sponsor)