After decades of chasing Jerry, Tom wants to make peace. Being skeptical, 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.
You are given:
- A 2D array of integers, maze, denoting the maze 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 locked stub code in your editor reads the following input from stdin and passes it to your function:
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.
Constraints
• 1 < n < 100
• 0< the number of cheese pieces <10
• 1 <x,y< n
Output Format:
Your function must 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 = 1Output: 1
How does one think of a DP approach for this? We have avoid 1’s and move towards all 2’s in the minimum number of steps.