Bloomberg VO 面试真题解析：Count Ships in a Rectangle（递归分治 / 几何搜索）

You work on a project that has to implement a new ship discovering technology.

You are provided with the following 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;

这道题的核心是利用已给定的 <code>hasShips</code> 接口，在一个矩形区域内统计船只数量。由于不能直接访问船只坐标，通常需要采用递归分治：先判断当前区域是否可能存在船只，如果 <code>hasShips</code> 返回 <code>false</code> 就直接剪枝；如果区域缩小到单点，则根据是否有船返回 0 或 1；否则将矩形继续划分为多个子矩形，分别统计后求和。题目重点考察几何范围拆分、递归终止条件以及如何通过接口查询减少无效搜索。