Amazon uses small, Roomba-shaped robots, called "Drives". They deliver large stacks of products to human workers by following set paths around the warehouse.
The warehouse can be represented in the form of a cartesian plane, where robots are located at integral points of the form (x, y). When a product is to be delivered to some point (i, j), the nearest robot is sought and chosen. Thus if a robot is surrounded by other robots nearby, it will seldom be chosen for work. More formally, a robot is said to be idle if it has a robot located above, below, left, and right of it. It is guaranteed that no two robots are at the same location.
Given the locations of n robots, find the number of idle robots.
Function Description
Complete the function numIdleDrives in the editor below.
numIdleDrives has the following parameters:
int x[n]:x[i]is the x-coordinate of theithrobot, where0 ≤ i < n.int y[n]:y[i]is the y-coordinate of theithrobot, where0 ≤ i < n.
Returns
int: the number of idle robots
Example 1:
Input: x = [0, 0, 0, 0, 0, 1, 1, 1, 2, -1, -1, -2, -1], y = [-1, 0, 1, 2, -2, 0, 1, -1, 0, 1, -1, 0, 0]
Output: 5
Explanation:The cartesian plane with idle robots marked red can be represented as:The robots at locations (0, 0), (1, 0), (-1, -0), (0, 1), and (0, -1) are idle as they are surrounded by robots on all 4 sides.
Example 2:
Input: x = [1, 1, 1, 2, 2, 2, 2, 3, 3, 3], y = [1, 2, 3, 1, 2, 3, 5, 1, 2, 3]
Output: 2
Explanation:The 10 robots are arranged as follows:
The robot at (2, 2) is idle because it has robots at (1, 2), (3, 2), (2, 3), and (2, 1) directly to the left, right, up, and down respectively. The robot at (2, 3) is idle because it has robots at (1, 3), (3, 3), (2, 5), and (2, 2) directly to the left, right, up, and down respectively. There are 2 idle robots in this arrangement.
1 ≤ n ≤ 105-109 ≤ x[i], y[i] ≤ 109
input:
output: