Number of Ships in a Rectangle

To solve this problem, you can use a divide-and-conquer approach. You need to search for ships within the given rectangle by calling the provided hasShips method, and if a ship is present in the current rectangle, you need to further divide the rectangle into smaller parts to find the exact locations of the ships.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:

        # Base case: if the rectangle has no area, or there are no ships in the rectangle, return 0
        if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y or not sea.hasShips(topRight, bottomLeft):
            return 0

        # Base case: if the rectangle is a point, and there is a ship, return 1
        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
            return 1

        # Divide the rectangle into four parts
        mid_x = (topRight.x + bottomLeft.x) // 2
        mid_y = (topRight.y + bottomLeft.y) // 2

        # Recursively call countShips on each of the four parts
        count = 0
        count += self.countShips(sea, Point(mid_x, mid_y), bottomLeft)
        count += self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1))
        count += self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1))
        count += self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))

        return count

Key Takeaways:

The solution applies divide-and-conquer to explore different parts of the rectangle recursively.
By dividing the rectangle into smaller parts and calling hasShips on them, we can accurately determine the count of ships in the rectangle.
The constraints guarantee that there are at most 10 ships in the rectangle, and the algorithm will not make more than 400 calls to hasShips, adhering to the problem’s limitations.