Algorithm (Divide and Conquer)

1. Let $f(R)$ be the total number of ships in rectangle $R$. Then we have $$f(R)=\begin{cases} f(R_{\mathrm{bottomLeft}})+f(R_{\mathrm{topRight}})+f(R_{\mathrm{bottomRight}})+f(R_{\text{topLeft}}) & \text{if }\mathrm{hasShip}(R)=\text{true}\text{ and }\mathrm{len}\left(\text{diag}(R)\right)\geq 2\\\\ f(R_{\text{bottomLeft}})+f(R_{\text{bottomRight}}) & \text{if }\text{hasShip}(R)=\text{true}\text{ and }\text{len}(\text{diag}(R))=1\text{ and }\text{topRight}(R)=\text{bottomLeft}(R)+(1,0)\\\\ f(R_{\text{bottomLeft}})+f(R_{\text{topLeft}}) & \text{if }\text{hasShip}(R)=\text{true}\text{ and }\text{len}(\text{diag}(R))=1\text{ and }\text{topRight}(R)=\text{bottomLeft}(R)+(0,1)\\\\ 1 & \text{if hasShip}(R)=\text{true }\text{and }\text{len}(\text{diag}(R))=0\\\\ 0 & \text{if }\text{hasShip}(R)=\text{false} \end{cases}$$
2. The implementation is then routine.

Code (Cpp17)

namespace math::vector_operations {
template <typename T>
std::vector<T> operator+(const std::vector<T>& x, const std::vector<T>& y) {
  auto res = x;
  for (int i = 0; i < size(y); ++i)
    res[i] += y[i];
  return res;
};

template <typename T>
std::vector<T> operator/(const std::vector<T>& x, T y) {
  auto res = x;
  for (int i = 0; i < size(x); ++i)
    res[i] /= y;
  return res;
};
}  // end namespace math::vector_operations

class Solution {
 private:
  int distance(const std::vector<int>& topRight, const std::vector<int>& bottomLeft) {
    const int dx = topRight[0] - bottomLeft[0];
    const int dy = topRight[1] - bottomLeft[1];
    return dx * dx + dy * dy;
  };

 public:
  int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
    using std::vector;
    using namespace math::vector_operations;
    if (sea.hasShips(topRight, bottomLeft) and distance(topRight, bottomLeft) == 0)
      return 1;
    else if (not sea.hasShips(topRight, bottomLeft))
      return 0;
    else if (distance(topRight, bottomLeft) == 1 and topRight == bottomLeft + vector{1, 1})
      return countShips(sea, bottomLeft, bottomLeft)
             + countShips(sea, bottomLeft + vector{0, 1}, bottomLeft + vector{0, 1})
             + countShips(sea, bottomLeft + vector{1, 0}, bottomLeft + vector{1, 0})
             + countShips(sea, topRight, topRight);
    else if (distance(topRight, bottomLeft) == 1 and topRight == bottomLeft + vector{0, 1})
      return countShips(sea, bottomLeft, bottomLeft)
             + countShips(sea, bottomLeft + vector{0, 1}, bottomLeft + vector{0, 1});
    else if (distance(topRight, bottomLeft) == 1 and topRight == bottomLeft + vector{1, 0})
      return countShips(sea, bottomLeft, bottomLeft)
             + countShips(sea, bottomLeft + vector{1, 0}, bottomLeft + vector{1, 0});
    else {
      const auto center = (topRight + bottomLeft) / 2;
      return countShips(sea, center, bottomLeft)
             + countShips(sea, {topRight[0], center[1]}, {center[0] + 1, bottomLeft[1]})
             + countShips(sea, {center[0], topRight[1]}, {bottomLeft[0], center[1] + 1})
             + countShips(sea, topRight, center + vector{1, 1});
    }
  }
};