0 like 0 dislike
1,504 views

All past online assesments  of Adobe  can be found using the tag "adobe_oa" in the search bar.

| 1,504 views

0 like 0 dislike
Bob and Alice have teamed up on a game show. They won the first
round, allowing them access to a maze with hidden gold. If Bob can
collect all the gold coins and deliver them to Alice's position, they can
split the gold. Bob can move North⇆South or East⇆West as long as he
stays in the maze and the cell is not blocked. The task is to determine
the shortest path Bob can follow to collect all gold coins and deliver
them to Alice. If it is not possible, return -1.

You will be given an n &times; m array where each of the values &isin; {0, 1, 2}
representing open, blocked and open with a gold coin. Alice's position is
given as (x,y) = (row, column). Bob starts at the top left in cell (0, 0).

For example, maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is
represented as follows:

0 2 1
1 2 0
1 0 0

minMoves has the following parameter(s):
maze[maze[0][0],...maze[n-1][m-1]]: a 2D array of integers
x: an integer denoting Alice's row coordinate
y: an integer denoting Alice's column coordinate

Constraints
1 &le; n, m &le; 100
0 &le; the number of coins &le; 10
1 &le; x < n
1 &le; y < m

The first line contains an integer n, the numbers of rows in maze.
The second line contains an integer m, the number of columns in
maze.
Each of the next n lines contains m space-separated integers
describing the cells of each row in maze.
The next line contains an integer x.
The next line contains an integer, y.

Sample Input 0
3
3
0 2 0
0 0 1
1 1 1
1
1

Sample Output 0
2
Explanation 0
The shortest path Bob can take is (0, 0) &rarr; (0, 1) &rarr; (1, 1).

Sample Input 1
3
3
0 1 0
1 0 1
0 2 2
1
1

Sample Output 1
-1
Explanation 1
It is not possible for Bob to reach Alice, so we return &minus;1.

Sample Input 2

3
3
0 2 0
1 1 2
1 0 0
2
1
Sample Output 2
5
Explanation 2
The shortest path Bob can take is (0, 0) &rarr; (0, 1) &rarr; (0, 2) &rarr; (1, 2) &rarr; (2, 2) &rarr; (2, 1).
by Expert (34,270 points)