Bloomberg / VO 面试真题解析：Implement Ship Counting with hasShips（分治搜索）

You are working on a project that has to implement a new ship-discovering technology.

You are provided with the function:

struct Point {
    const int x;
    const int y;
    Point(int x, int y) : x_(x), y_(y) {}};

bool hasShips(const Point& bottom_left, const Point& top_right);
// Returns true if there are 1 or more ships within the area with corners bottom_left and top_right.
// Returns false if there are no ships within the area.

Using the hasShips function, implement the function:

int countShips(const Point& bottom_left, const Point& top_right);
// Returns the number of ships there are within the area with corners bottom_left and top_right

Sample inputs – Expected outputs:

"X" marks the presence of a ship. A, B, and C are points defined below.

Point A (0, 0)
Point B (0, 3)
Point C (2, 3)

hasShips(A, C) == true;
hasShips(B, C) == false;
hasShips(C, C) == false;

countShips(A, C) == 2;
countShips(B, C) == 0;
countShips(C, C) == 0;

这道题的核心是利用系统提供的 hasShips(bottom_left, top_right) 接口做分治搜索，统计矩形区域内的船只数量。由于不能直接看到每个点是否有船，只能通过“这个子区域是否至少有一艘船”来剪枝，因此最自然的做法是把当前矩形不断二分成更小的子矩形，先用 hasShips 判断子区域是否值得继续搜索；如果返回 false，就可以直接跳过。若缩小到单个点时再判断是否计数。这个题重点考察区域分治、递归边界处理以及如何减少 API 调用次数，通常需要注意坐标区间的划分方式和避免重复覆盖。