Number of Ships in a Rectangle

Problem Statement

In this interactive problem, the challenge is to determine the number of ships located within a designated rectangular area on a Cartesian plane, where each integer point on the plane can host at most one ship. The primary tool at your disposal is a provided function Sea.hasShips(topRight, bottomLeft), which confirms whether there is at least one ship in the rectangle defined by its two corner points: topRight and bottomLeft.

The task is to accurately count the ships in the rectangle using the function, with the added condition that there cannot be more than 10 ships in any queried rectangle. Critical to the approach is the limitation that the function cannot be called more than 400 times per solution attempt. Attempting to bypass these restrictions programmatically will lead to disqualification.

Examples

Example 1

Input:

ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]

Output:

3

Explanation:

From [0,0] to [4,4] we can count 3 ships within the range.

Example 2

Input:

ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,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

Approach and Intuition

Given the constraints and nature of the problem, the solution approaches this as a classic search problem, specifically one that can be tackled effectively with a "divide and conquer" strategy. Here is how one could structure the steps:

1. Using the Sea.hasShips Function:

   • Begin by querying the entire rectangle defined by topRight and bottomLeft using the Sea.hasShips function. If the function returns false, then there are no ships in the rectangle, and you can return 0.
   • If the function returns true, indicating that there is at least one ship in the rectangle, proceed to split the rectangle into smaller sections.

2. Divide and Conquer Approach:

   • Find the midpoint of each dimension of the rectangle (x and y axes). This will allow the rectangle to be divided into four smaller rectangles.
   • Recursively apply the hasShips function to each of these smaller rectangles.
   • If a rectangle is found to contain no ships (hasShips returns false), no further subdivision or checks are needed for that section.
   • Continue subdividing until rectangles are sufficiently small or until further subdivision is not feasible given the query limits.

3. Aggregation and Count Restriction:

   • As the recursive function returns, aggregate the counts from each quadrant.
   • Ensure that the number of API calls does not exceed 400 to avoid a wrong answer judgment.

The recursive division helps in narrowing down the areas to precisely locate ships without excessive querying, adhering to the constraints provided. The challenge lies in optimizing the query distribution to not only stay within the allowed number of calls but also cover the search space effectively. This approach also works well given the guarantee that no more than 10 ships will be within any given query rectangle, making deeper divisions of the space more fruitful as the recursion progresses.

Solutions

class Solution {
public:
    int shipCount(Sea ocean, vector<int> upperRight, vector<int> lowerLeft) {
        if (lowerLeft[0] > upperRight[0] || lowerLeft[1] > upperRight[1])
            return 0;
        if (!ocean.hasShips(upperRight, lowerLeft))
            return 0;
    
        if (upperRight[0] == lowerLeft[0] && upperRight[1] == lowerLeft[1])
            return 1;
    
        int centerX = (upperRight[0] + lowerLeft[0]) / 2;
        int centerY = (upperRight[1] + lowerLeft[1]) / 2;
        return shipCount(ocean, {centerX, centerY}, lowerLeft) +
               shipCount(ocean, upperRight, {centerX + 1, centerY + 1}) +
               shipCount(ocean, {centerX, upperRight[1]}, {lowerLeft[0], centerY + 1}) +
               shipCount(ocean, {upperRight[0], centerY}, {centerX + 1, lowerLeft[1]});
    }
};