GTS OA Interview Problem: Min Moves

Min Moves

Chris and Alex are in a game show where they navigate a maze with hidden gold coins. Chris must collect all gold coins and deliver them to Alex’s location. Chris can move horizontally or vertically within the maze through unblocked cells.

The maze is represented as an n x m grid. Each cell can be one of three values:

• 0: Open cell
• 1: Blocked cell
• 2: Open cell with a gold coin

Chris starts at position (0, 0), and Alex is at a specified position (x, y).

Return the length of the shortest path for Chris to collect all gold coins and reach Alex. If it is not possible to collect all coins and reach Alex, return -1.

Example

maze = [[0,2,1],[1,2,0],[0,0,0]] with Alex at (2,2)
The shortest possible path length is 4.

Function Description

Complete the function minMoves in the editor with the following parameter(s):

• int maze[n][m]: a 2D array of integers
• int x: Alex’s row coordinate
• int y: Alex’s column coordinate

Returns

• int: length of Chris’s shortest path, or -1 if it is not possible

Constraints

• 1 ≤ n, m ≤ 100
• 0 ≤ the number of coins ≤ 10
• 1 ≤ x < n
• 1 ≤ y < m

This problem combines grid shortest paths with state tracking. Since there are at most 10 coins, the key is to treat“which coins have been collected”as part of the state rather than running a plain BFS from start to end. A common solution is to first compute shortest distances between the start, every coin, and Alex’s position, then use bitmask DP or state-space search to find the minimum total path that visits all coins and finishes at the target. If any required point is unreachable, the answer is -1.