Netflix OA 面试真题解析：二维地图寻路并收集所有旗帜

You must develop an algorithm to navigate a car through an optimal path while hitting every flag in the graph.

You can gain points by:

• Giving a valid path that hits all flags
• Giving the optimal path

Note: All tests run back-to-back under a single total time limit. To be scored, your solution must return an output—correct or not—for every test case within that total time. If the total time limit is exceeded, the entire submission receives 0 points.

You can add your own test paths to user-defined-tracks.json.

Input

You will be given a 2D track in the form of a two-dimensional array. You will be given a starting square, the location of the flags, and the navigable squares in the track.

Spaces within the track can be one of the following values:

• S — The starting space
• F — Flags (navigable)
• 1 — Navigable space
• 0 — Out of bounds space

An example input (Simple track):

Output

You must return an object with an array called moves. The accepted values are RIGHT, LEFT, UP, and DOWN.

The optimal path for the Simple Track can be solved in 13 moves:

这道 Netflix OA 题的核心是：在一个二维网格赛道中，从起点出发，按最短或尽量优的路径依次经过所有旗帜。网格里只有四种格子：起点 S、旗帜 F、可通行格子 1、不可通行格子 0；你需要输出由 RIGHT、LEFT、UP、DOWN 组成的移动序列。由于要同时兼顾“能走通”和“尽可能最优”，常见做法是先用 BFS 在关键点之间求最短路，再把“起点 + 所有旗帜”抽象成图上的节点，做状态压缩 DP / TSP 式搜索；当旗帜数量较少时尤其适用。若数据规模很大，通常还需要结合启发式搜索或优先级策略来保证在时间限制内返回结果。