,0] Output: 3

Constraints:

On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000
topRight != bottomLeft

Solution

Method 1 – Divide and Conquer (Quad Tree)

Intuition

Since the number of ships is small and the area is large, we use divide and conquer. We recursively split the rectangle into four smaller rectangles and use the hasShips API to prune empty regions. If a region is a single point and has a ship, we count it. This minimizes the number of API calls.

Approach

If hasShips(topRight, bottomLeft) is false, return 0.
If topRight == bottomLeft, return 1 (there is a ship at this point).
Otherwise, split the rectangle into four smaller rectangles by dividing both x and y in half.
Recursively count ships in each subrectangle and sum the results.
Return the total count.

Code

[{"language":"C++","code":"// This is the Sea's API interface.\n// class Sea {\n//   public:\n//     bool hasShips(vector<int> topRight, vecto

Related Tags