GTS OA 面试真题解析：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

这道题的核心是“网格最短路 + 状态搜索”。因为金币数量最多只有 10 个，所以不能只用普通 BFS 直接从起点搜到终点，而要把“已经收集了哪些金币”也作为状态的一部分，通常用 BFS/ 最短路预处理出关键点之间的距离，再配合位压缩动态规划或状态图搜索，枚举从起点出发依次收集金币并到达 Alex 的最短总代价。若起点、金币或终点之间存在不可达路径，就返回 -1。