Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

👨‍💻 Алгоритм:

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

3⃣Суммируйте количество кораблей в подпрямоугольниках для получения общего количества кораблей в текущем прямоугольнике.

😎 Решение:

class Solution {
    func countShips(_ sea: Sea, _ topRight: Point, _ bottomLeft: Point) -> Int {
        if !sea.hasShips(topRight, bottomLeft) {
            return 0
        }
        if topRight.x == bottomLeft.x && topRight.y == bottomLeft.y {
            return 1
        }
        let midX = (topRight.x + bottomLeft.x) / 2
        let midY = (topRight.y + bottomLeft.y) / 2
        return countShips(sea, Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, Point(midX + 1, midY + 1)) +
               countShips(sea, Point(midX, topRight.y), Point(bottomLeft.x, midY + 1)) +
               countShips(sea, Point(topRight.x, midY), Point(midX + 1, bottomLeft.y))
    }
}

Ставь 👍 и забирай 📚 Базу знаний