## Number of Ships in a Rectangle

• Time:O(\log mn)
• Space:O(\log mn)

## C++

/**
* // 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 {
public:
int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1])
return 0;
if (!sea.hasShips(topRight, bottomLeft))
return 0;

// sea.hashShips(topRight, bottomLeft) == true
if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
return 1;

const int mx = (topRight[0] + bottomLeft[0]) / 2;
const int my = (topRight[1] + bottomLeft[1]) / 2;
int ans = 0;
// top right
ans += countShips(sea, topRight, {mx + 1, my + 1});
// bottom right
ans += countShips(sea, {topRight[0], my}, {mx + 1, bottomLeft[1]});
// top left
ans += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my + 1});
// bottom left
ans += countShips(sea, {mx, my}, bottomLeft);
return ans;
}
};

## JAVA

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

class Solution {
public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1])
return 0;
if (!sea.hasShips(topRight, bottomLeft))
return 0;

// sea.hashShips(topRight, bottomLeft) == true
if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
return 1;

final int mx = (topRight[0] + bottomLeft[0]) / 2;
final int my = (topRight[1] + bottomLeft[1]) / 2;
int ans = 0;
// top right
ans += countShips(sea, topRight, new int[] {mx + 1, my + 1});
// bottom right
ans += countShips(sea, new int[] {topRight[0], my}, new int[] {mx + 1, bottomLeft[1]});
// top left
ans += countShips(sea, new int[] {mx, topRight[1]}, new int[] {bottomLeft[0], my + 1});
// bottom left
ans += countShips(sea, new int[] {mx, my}, bottomLeft);
return ans;
}
}

## Python

# """
# 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):
def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y:
return 0
if not sea.hasShips(topRight, bottomLeft):
return 0

# sea.hashShips(topRight, bottomLeft) == True
if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
return 1

mx = (topRight.x + bottomLeft.x) // 2
my = (topRight.y + bottomLeft.y) // 2
ans = 0
# top right
ans += self.countShips(sea, topRight, Point(mx + 1, my + 1))
# bottom right
ans += self.countShips(sea, Point(topRight.x, my),
Point(mx + 1, bottomLeft.y))
# top left
ans += self.countShips(sea, Point(mx, topRight.y),
Point(bottomLeft.x, my + 1))
# bottom left
ans += self.countShips(sea, Point(mx, my), bottomLeft)
return ans