题目重点:车在网格中带初始 gas,经过补给点增加油量,判断能否到绿洲;分清可重复领油与一次性站点。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版四方向移动,每步耗 1 油,障碍不可走,车与绿洲唯一;油站在本次路径中至多领一次。
- 如果站点重访可无限重复领油,存在可泵油的循环,问题模型完全不同;需先问清,不用简单 BFS 的 cell visited 蒙混。
解题路线
- K 个一次性油站编号,用状态 (r,c,remainingGas,usedStationsBitmask);起点带初始 gas。
- 移动到邻格先耗 1,若是尚未领过的油站则加站点值、置对应 bit;目标出队/入队时即可判断可达。
- 对状态做 visited;同坐标但不同剩余油或领站历史不可直接合并,回头路可能通向原先到不了的绿洲。
- 对小 K 用 BFS/DFS 即可;K 很大时需用路径/资源问题的支配关系或额外约束,不能承诺简单多项式解。
手动走一遍
训练例:起点油 2,绿洲距离 4,中途偏离直线 1 步有 +3 油站;若能绕路抵站并返回,带油状态会使原本因油不足被判失败的坐标重新可探索。具体地图由原题决定。
规模与取舍
设网格 RC、站点 K、最大可用油 G=初始油+所有站油,朴素状态上界 O(RC·(G+1)·2^K),每状态常数邻居;只是小规模正确性基线,不适于 K 大的情况。
易错点与追问
容易失分的边界
- 只给每个 cell 一个 visited bool。
- 允许无限重复领取一次性油站。
- 把曼哈顿距离≤gas 当作有障碍/补给的完整答案。
- 忽略走回头路或起点/终点也可能有站点。
继续深挖
- 站点可重复领取会怎样?
- 如果只求最少步数?
- 油箱容量有限怎么办?
- 如何安全剪枝同位置的状态?
