Задача: 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⃣Суммируйте количество кораблей в подпрямоугольниках для получения общего количества кораблей в текущем прямоугольнике.

😎 Решение:

var countShips = function(sea, topRight, bottomLeft) {
    if (!sea.hasShips(topRight, bottomLeft)) {
        return 0;
    }
    if (topRight.x === bottomLeft.x && topRight.y === bottomLeft.y) {
        return 1;
    }
    const midX = Math.floor((topRight.x + bottomLeft.x) / 2);
    const midY = Math.floor((topRight.y + bottomLeft.y) / 2);
    return countShips(sea, {x: midX, y: midY}, bottomLeft) +
           countShips(sea, topRight, {x: midX + 1, y: midY + 1}) +
           countShips(sea, {x: midX, y: topRight.y}, {x: bottomLeft.x, y: midY + 1}) +
           countShips(sea, {x: topRight.x, y: midY}, {x: midX + 1, y: bottomLeft.y});
};

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