Converging Maze: Nearest meeting cell
Learn this problemProblem statement
You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit
(ie. entry/exit points are unidirectional doors like valves).
The cells are named with an integer value from 0 to N-1.
You have to find:
Nearest meeting cell:
Given any two cells, src and dest, find a cell that can be reached from both. For each common reachable cell, consider the larger of its distances from src and dest. Return the cell that minimizes this distance. If multiple cells are tied, return the cell with the smallest number. Return -1 when no cell is reachable from both starts.
Function
nearestMeetingCell(arr: int[], src: int, dest: int) → int
Complete nearestMeetingCell with the following parameters:
int[] arr: an array of lengthN, wherearr[i]is the cell reached from celliin one step, or-1when cellihas no exit. The value ofNisarr.length.int src: the first starting cellint dest: the second starting cell
Returns
int: the nearest meeting cell, or -1 if no meeting cell exists
🍀 Endless thanks to the friend who generously helped!
Examples
Example 1
arr = [4, 4, 1, 4, 13, 8, 8, 8, 0, 8, 14, 9, 15, 11, -1, 10, 15, 22, 22, 22, 22, 22, 21]src = 9dest = 2return = 4Constraints
1 ≤ arr.length ≤ 105-1 ≤ arr[i] < arr.length0 ≤ src, dest < arr.length