# 1274. Number of Ships in a Rectangle

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

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.

# Solution

Approach 1: recursion (divided and conquer).

# Code (Python)

Approach 1:

class Solution(object):
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        # idea: recursion (divide and conquer) -- point definition is awkward, so have to translate between Point and coord
        # https://leetcode.com/problems/number-of-ships-in-a-rectangle/discuss/440884/Python
        def count(p1, p2):
            x, X = p1
            y, Y = p2
            if x > X or y > Y or not sea.hasShips(Point(X, Y), Point(x, y)):
                return 0
            if (x, y) == (X, Y):
                return 1
            xm = (x + X) // 2
            ym = (y + Y) // 2
            xRanges = (x, xm), (xm+1, X)
            yRanges = (y, ym), (ym+1, Y)
            return sum(count(xr, yr) for xr in xRanges for yr in yRanges)
        
        return count((bottomLeft.x, topRight.x), (bottomLeft.y, topRight.y))

# Code (C++)

Approach 1:

Approach 2: