Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1274.html

1274. Number of Ships in a Rectangle

Level

Hard

Description

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example:

Image text

Input:

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

Output: 3

Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Constraints:

  • On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
  • 0 <= bottomLeft[0] <= topRight[0] <= 1000
  • 0 <= bottomLeft[1] <= topRight[1] <= 1000

Solution

Use recursion and the idea of divide and conquer. The base case is that topRight and bottomLeft are the same, and there is only one point in the rectangle. In this case, call Sea.hasShips(topRight, bottomLeft) to obtain the result. If the result is true, return 1. If the result is false, return 0.

If topRight and bottomLeft have the same x-axis value, then obtain midY = (topRight[1] + bottomLeft[1]) / 2 and divide the rectangle into 2 parts. For each part, first call Sea.hasShips(topRight, bottomLeft) to see whether there are ships in the rectangle. If the result is false, then there is no need to obtain the number of ships in the rectangle. Only if the result is true, the number of ships in the rectangle is needed. Obtain the number of ships in the rectangle recursively.

If topRight and bottomLeft have the same y-axis value, then obtain midX = (topRight[0] + bottomLeft[0]) / 2 and divide the rectangle into 2 parts. Obtain the number of ships similar to the case where topRight and bottomLeft have the same x-axis value.

In other cases, obtain midX = (topRight[0] + bottomLeft[0]) / 2 and midY = (topRight[1] + bottomLeft[1]) / 2, and divide the rectangle into 4 parts. For each part, first call Sea.hasShips(topRight, bottomLeft) to see whether there are ships in the rectangle. If the result is false, then there is no need to obtain the number of ships in the rectangle. Only if the result is true, the number of ships in the rectangle is needed. Obtain the number of ships in the rectangle recursively.

  • /**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *     public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
            return sea.hasShips(topRight, bottomLeft) ? 1 : 0;
        else if (topRight[0] == bottomLeft[0]) {
            int midY = (topRight[1] + bottomLeft[1]) / 2;
            int[] topRightMid = {topRight[0], midY};
            int[] bottomLeftMid = {bottomLeft[0], midY + 1};
            int ships = 0;
            if (sea.hasShips(topRightMid, bottomLeft))
                ships += countShips(sea, topRightMid, bottomLeft);
            if (sea.hasShips(topRight, bottomLeftMid))
                ships += countShips(sea, topRight, bottomLeftMid);
            return ships;
        } else if (topRight[1] == bottomLeft[1]) {
            int midX = (topRight[0] + bottomLeft[0]) / 2;
            int[] topRightMid = {midX, topRight[1]};
            int[] bottomLeftMid = {midX + 1, bottomLeft[1]};
            int ships = 0;
            if (sea.hasShips(topRightMid, bottomLeft))
                ships += countShips(sea, topRightMid, bottomLeft);
            if (sea.hasShips(topRight, bottomLeftMid))
                ships += countShips(sea, topRight, bottomLeftMid);
            return ships;
        } else {
            int midX = (topRight[0] + bottomLeft[0]) / 2, midY = (topRight[1] + bottomLeft[1]) / 2;
            int[] topRight1 = {midX, midY};
            int[] bottomLeft1 = {bottomLeft[0], bottomLeft[1]};
            int[] topRight2 = {topRight[0], midY};
            int[] bottomLeft2 = {midX + 1, bottomLeft[1]};
            int[] topRight3 = {midX, topRight[1]};
            int[] bottomLeft3 = {bottomLeft[0], midY + 1};
            int[] topRight4 = {topRight[0], topRight[1]};
            int[] bottomLeft4 = {midX + 1, midY + 1};
            int ships = 0;
            if (sea.hasShips(topRight1, bottomLeft1))
                ships += countShips(sea, topRight1, bottomLeft1);
            if (sea.hasShips(topRight2, bottomLeft2))
                ships += countShips(sea, topRight2, bottomLeft2);
            if (sea.hasShips(topRight3, bottomLeft3))
                ships += countShips(sea, topRight3, bottomLeft3);
            if (sea.hasShips(topRight4, bottomLeft4))
                ships += countShips(sea, topRight4, bottomLeft4);
            return ships;
        }
    }
}

  • /**
 * // 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 (!sea.hasShips(topRight, bottomLeft))
      return 0;

    // Sea.hashShips(topRight, bottomLeft) == true
    if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
      return 1;

    const int mx = (topRight[0] + bottomLeft[0]) / 2;
    const int my = (topRight[1] + bottomLeft[1]) / 2;
    int ans = 0;
    // Top right
    ans += countShips(sea, topRight, {mx + 1, my + 1});
    // Bottom right
    ans += countShips(sea, {topRight[0], my}, {mx + 1, bottomLeft[1]});
    // Top left
    ans += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my + 1});
    // Bottom left
    ans += countShips(sea, {mx, my}, bottomLeft);
    return ans;
  }
};


  • # """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
# Class Sea(object):
#   def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
# Class Point(object):
#   def __init__(self, x: int, y: int):
#       self.x = x
#       self.y = y

class Solution(object):
  def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
    if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y:
      return 0
    if not sea.hasShips(topRight, bottomLeft):
      return 0

    # Sea.hashShips(topRight, bottomLeft) == True
    if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:
      return 1

    mx = (topRight.x + bottomLeft.x) // 2
    my = (topRight.y + bottomLeft.y) // 2
    ans = 0
    # Top right
    ans += self.countShips(sea, topRight, Point(mx + 1, my + 1))
    # Bottom right
    ans += self.countShips(sea, Point(topRight.x, my),
                           Point(mx + 1, bottomLeft.y))
    # Top left
    ans += self.countShips(sea, Point(mx, topRight.y),
                           Point(bottomLeft.x, my + 1))
    # Bottom left
    ans += self.countShips(sea, Point(mx, my), bottomLeft)
    return ans

All Problems

All Solutions