NG SWE · Phone / Campus Onsite Coding

Bloomberg 沙漠网格加油站:带油量与领油历史的可达性

车在网格中带初始 gas,经过补给点增加油量,判断能否到绿洲;分清可重复领油与一次性站点。

题目重点:车在网格中带初始 gas,经过补给点增加油量,判断能否到绿洲;分清可重复领油与一次性站点。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练版四方向移动,每步耗 1 油,障碍不可走,车与绿洲唯一;油站在本次路径中至多领一次。
  • 如果站点重访可无限重复领油,存在可泵油的循环,问题模型完全不同;需先问清,不用简单 BFS 的 cell visited 蒙混。

解题路线

  1. K 个一次性油站编号,用状态 (r,c,remainingGas,usedStationsBitmask);起点带初始 gas。
  2. 移动到邻格先耗 1,若是尚未领过的油站则加站点值、置对应 bit;目标出队/入队时即可判断可达。
  3. 对状态做 visited;同坐标但不同剩余油或领站历史不可直接合并,回头路可能通向原先到不了的绿洲。
  4. 对小 K 用 BFS/DFS 即可;K 很大时需用路径/资源问题的支配关系或额外约束,不能承诺简单多项式解。

手动走一遍

训练例:起点油 2,绿洲距离 4,中途偏离直线 1 步有 +3 油站;若能绕路抵站并返回,带油状态会使原本因油不足被判失败的坐标重新可探索。具体地图由原题决定。

规模与取舍

设网格 RC、站点 K、最大可用油 G=初始油+所有站油,朴素状态上界 O(RC·(G+1)·2^K),每状态常数邻居;只是小规模正确性基线,不适于 K 大的情况。

易错点与追问

容易失分的边界

  • 只给每个 cell 一个 visited bool。
  • 允许无限重复领取一次性油站。
  • 把曼哈顿距离≤gas 当作有障碍/补给的完整答案。
  • 忽略走回头路或起点/终点也可能有站点。

继续深挖

  • 站点可重复领取会怎样?
  • 如果只求最少步数?
  • 油箱容量有限怎么办?
  • 如何安全剪枝同位置的状态?
✓已复制微信号!