Advertisement
Guest User

Untitled

a guest
Feb 9th, 2022
40
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * // This is Sea's API interface.
  3.  * // You should not implement it, or speculate about its implementation
  4.  * class Sea {
  5.  *   public:
  6.  *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
  7.  * };
  8.  */
  9.  
  10. class Solution {
  11. public:
  12.     int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
  13.         if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1]) {
  14.             return 0;
  15.         }
  16.        
  17.         if (topRight == bottomLeft) {
  18.             return sea.hasShips(topRight, bottomLeft);
  19.         }
  20.        
  21.         if (!sea.hasShips(topRight, bottomLeft)) {
  22.             return 0;
  23.         }
  24.        
  25.         vector<int> middle = {(topRight[0] + bottomLeft[0]) / 2, (topRight[1] + bottomLeft[1]) / 2};
  26.        
  27.         return countShips(sea, topRight, {middle[0] + 1, middle[1] + 1}) +
  28.                countShips(sea, {topRight[0], middle[1]}, {middle[0] + 1, bottomLeft[1]}) +
  29.                countShips(sea, {middle[0], topRight[1]}, {bottomLeft[0], middle[1] + 1}) +
  30.                countShips(sea, middle, bottomLeft);
  31.     }
  32. };
Advertisement
RAW Paste Data Copied
Advertisement