A retail store chain wants to expand into a new neighbourhood. To make the number of clients as large as possible, the new branch should be at a distance of no more than K from all the houses in the neighborhood. A is the matrix of size N * M. It represents the neighbourhood as a rectangular grid, in which each cell is an integer 0 (an empty plot) and 1 (a house). The distance between two cells is calculated as the minimum number of cell borders that one has to cross to move from the source cell to the target cell. It doesn't matter whether the cells on the way are empty or occupied, but it doesn't allow for moving through corners. A store can be built on an empty plot. How many suitable locations are there?
Function Description
Complete the function findSuitableLocations in the editor.
findSuitableLocations has the following parameters:
- 1.
int[][] A: a matrix representing the neighborhood - 2.
int K: the maximum distance from all houses
Returns
int: the number of empty plots close enough to all the houses
Example 1:
Input: A = [[0,0,0,0],[0,0,1,0],[1,0,0,1]], K = 2
Output: 2
Explanation:GivenK=2and matrixA=[[0,0,0,0],[0,0,1,0],[1,0,0,1]], houses are located in the cells with coordinates (2,3), (3,1), and (3,4). We can build a new store on two empty plots that are close enough to all the houses. The first possible empty plot is located at (3,2); the distance to the first house at (2,3) is 2, to the second house at (3,1) is 1, and to the third house at (3,4) is 2. The second possible empty plot is located at (3,3). The distance to the first, second, and third houses are 1, 2, and 1, respectively. Given the positive integerKand matrixAof sizeN*M, the function should return 2.
N/A
input:
output: