LeetCode 1274. 矩形内船只的数目（分治）

输入：
ships = [[1,1],[2,2],[3,3],[5,5]], 
topRight = [4,4], bottomLeft = [0,0]
输出：3
解释：在 [0,0] 到 [4,4] 的范围内总共有 3 艘船。
 
提示：
ships 数组只用于评测系统内部初始化。
你无法得知 ships 的信息，所以只能通过调用 hasShips 接口来求解。
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public:
 *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution { //C++
	int sum = 0;
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
    	if(topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1]
                || !sea.hasShips(topRight, bottomLeft))
    		return 0;
        if(topRight == bottomLeft)
    		return ++sum;
        int xmid = (topRight[0] + bottomLeft[0])/2;
        int ymid = (topRight[1] + bottomLeft[1])/2;
        countShips(sea, {xmid, ymid}, bottomLeft);
        countShips(sea,  {topRight[0], ymid}, {xmid+1, bottomLeft[1]});
        countShips(sea, {xmid, topRight[1]}, {bottomLeft[0], ymid+1});
        countShips(sea, topRight, {xmid+1, ymid+1});
        return sum;
    }
};

# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Sea(object):
#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
#class Point(object):
#   def __init__(self, x: int, y: int):
#       self.x = x
#       self.y = y

class Solution(object): #py3
    def __init__(self):
        self.sum = 0
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y or not sea.hasShips(topRight, bottomLeft):
            return 0
        xmid = (topRight.x + bottomLeft.x)//2
        ymid = (topRight.y + bottomLeft.y)//2
        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
            self.sum += 1
            return self.sum
        self.countShips(sea, Point(xmid, ymid), bottomLeft)
        self.countShips(sea, Point(topRight.x, ymid), Point(xmid+1, bottomLeft.y))
        self.countShips(sea, Point(xmid, topRight.y), Point(bottomLeft.x, ymid+1))
        self.countShips(sea, topRight, Point(xmid+1, ymid+1))
        return self.sum