FastPrepFastPrep
Problem Brief

Converging Maze: Nearest meeting cell

NEW GRADOA

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 - C1, C2, find the closest cell Cm that can be reached from both C1 and C2.

Function Description

You are given a function Solution containing arr[N], src, desc as inputs.

Complete the code in the function and return the answer from it.

Input Format

  • An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines.
  • The first line of each testcase has the number of cells N
  • The second line of each testcase has a list of N values of the edge[] array. edge[i] contains the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the i'th cell doesn't have an exit.
  • Third line for each testcase contains two cell numbers whose nearest meeting cell needs to be found. (return -1 if there is no meeting cell from the two given cells)

    • Output Format

    For each testcase given, output a single line that denotes the nearest meeting cell (NMC)

    🍀 Endless thanks to the friend who generously helped!

    1Example 1

    Input
    n = 23, 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 = 9, dest = 2
    Output
    4
    Explanation
    oo
    public int nearestMeetingCell(int[] arr, int src, int dest) {
  // write your code here
}
    Input

    n

    23

    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

    9

    dest

    2

    Output

    4

    Sign in to submit your solution.