/**
 * // 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 (topRight == bottomLeft) {
            return sea.hasShips(topRight, bottomLeft);
        }

        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }

        vector<int> middle = {(topRight[0] + bottomLeft[0]) / 2, (topRight[1] + bottomLeft[1]) / 2};

        return countShips(sea, topRight, {middle[0] + 1, middle[1] + 1}) +
               countShips(sea, {topRight[0], middle[1]}, {middle[0] + 1, bottomLeft[1]}) +
               countShips(sea, {middle[0], topRight[1]}, {bottomLeft[0], middle[1] + 1}) +
               countShips(sea, middle, bottomLeft);
    }
};