# LeetCode: 1274. 矩形内船只的数目¶

## 1、题目描述¶

(此题是 交互式问题 )

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



• ships 数组只用于评测系统内部初始化。你无法得知 ships 的信息，所以只能通过调用 hasShips 接口来求解。
• $0 <= bottomLeft[0] <= topRight[0] <= 1000$
• $0 <= bottomLeft[1] <= topRight[1] <= 1000$

## 2、解题思路¶

• 分治法
• 首先进行横坐标区间的切分，当横坐标切分到相等之后，进行纵坐标切分
• 最后只有一个点的时候不切分，直接计算是否存在即可
# """
# 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 and topRight.y == bottomLeft.y:
return 1 if sea.hasShips(topRight, bottomLeft) else 0

ans = 0
if topRight.x > bottomLeft.x:
scope = topRight.x - bottomLeft.x
mid_x = bottomLeft.x + scope // 2
mid_left = Point(mid_x, topRight.y)
mid_right = Point(mid_x + 1, bottomLeft.y)
if sea.hasShips(mid_left, bottomLeft):
ans += self.countShips(sea, mid_left, bottomLeft)
if sea.hasShips(topRight, mid_right):
ans += self.countShips(sea, topRight, mid_right)
return ans

scope = topRight.y - bottomLeft.y
mid_bottom = Point(bottomLeft.x, bottomLeft.y + scope // 2)
mid_up = Point(bottomLeft.x, bottomLeft.y + scope // 2 + 1)

if sea.hasShips(mid_bottom, bottomLeft):
ans += self.countShips(sea, mid_bottom, bottomLeft)
if sea.hasShips(topRight, mid_up):
ans += self.countShips(sea, topRight, mid_up)
return ans


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

class Sea(object):
def __init__(self, p):
self.count = 0
self.points = set([tuple(x) for x in p])

def hasShips(self, topRight: Point, bottomLeft: Point) -> bool:
self.count += 1
for x in range(bottomLeft.x, topRight.x + 1):
for y in range(bottomLeft.y, topRight.y + 1):
if (x, y) in self.points:
return True
return False

class Solution(object):
def countShips(self, sea: Sea, topRight: Point, bottomLeft: Point) -> int:
if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
return 1 if sea.hasShips(topRight, bottomLeft) else 0

ans = 0
if topRight.x > bottomLeft.x:
scope = topRight.x - bottomLeft.x
mid_x = bottomLeft.x + scope // 2
mid_left = Point(mid_x, topRight.y)
mid_right = Point(mid_x + 1, bottomLeft.y)
if sea.hasShips(mid_left, bottomLeft):
ans += self.countShips(sea, mid_left, bottomLeft)
if sea.hasShips(topRight, mid_right):
ans += self.countShips(sea, topRight, mid_right)
return ans

scope = topRight.y - bottomLeft.y
mid_bottom = Point(bottomLeft.x, bottomLeft.y + scope // 2)
mid_up = Point(bottomLeft.x, bottomLeft.y + scope // 2 + 1)

if sea.hasShips(mid_bottom, bottomLeft):
ans += self.countShips(sea, mid_bottom, bottomLeft)
if sea.hasShips(topRight, mid_up):
ans += self.countShips(sea, topRight, mid_up)
return ans

points = [[1, 1], [2, 2], [3, 3], [5, 5]]
s = Sea(points)

solution = Solution()
print(solution.countShips(s, Point(100, 100), Point(0, 0)))
print(s.count)