After decades of chasing Jerry, Tom wants to make peace. Being sceptical, Jerry hides in an n x n maze. Tom decides the best way to make Jerry take him seriously is to collect all of the cheese pieces in the maze and give them to Jerry as a gift. A move is considered to be a single step from the current position to some adjacent position in the maze. Tom can move in all four directions within the maze: up, down, left and right.
Given:
A 2D array of integers denoting the maze (0 denotes path,2 denotes presence of cherry and 1 denotes path is blocked) where Jerry is hiding.
An integer, x, denoting the x-coordinate for Jerry’s location.
An integer, y, denoting the y-coordinate Jerry’s location.
Tom’s initial position is (0, 0). Your function must return an integer denoting the minimum number of moves that it will take for him to collect all the cheese and deliver it to Jerry at (x, y); if the task is not possible, return -1.
Input format:
The first line contains an integer, n, denoting the number of rows in maze.
The second line contains an integer, n, denoting the number of columns in maze.
Each line l of the n subsequent lines (where 0 < l < n) contains n space-separated integers describing the respective elements of row / in maze.
The next line contains an integer, x, denoting the x-coordinate where Jerry is located in maze.
The next line contains an integer, y, denoting the y-coordinate where Jerry is located in maze.
Output Format:
Return an integer denoting the minimum number of moves Tom must make to collect all of the maze’s cheese and deliver it to Jerry; if the task is not possible, return -1.
Example:
Input:
Maze = {0, 2, 0}, {0, 0, 1}, {1, 1, 1}
x = 1, y = 1
Output: 1
Can anyone share approach for this.