Last Updated: 30 Mar, 2021
##### Farthest Distance From Lands
Moderate
Problem statement

#### Note :

``````The distance between any two cells (x0, y0) and (x1, y1) is given by the Manhattan distance: |x0 - x1| + |y0 - y1|.
If no land or water exists in the grid, then return -1.
``````
##### Input Format :
``````The first line of input contains an integer βT' representing the number of test cases.

The first line of each test case contains one integer βNβ denoting the size of the matrix.

The next βNβ lines contain βNβ integers separated by spaces describing rows of matrix βARRβ (each element of βARRβ is either 0 or 1).
``````
##### Output Format :
``````For each test case, on a separate line, output one integer - the largest distance from a water cell to the nearest land cell.
``````
##### Note :
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^3
ARR[i][j] = 0 or 1

Time limit: 1 sec
``````
Approaches

## 01Approach

The idea here is to calculate the distance from each land cell and update every water cell to the minimum distance via any land cell.

We declare a 2d matrix minDistance[][] initially set to Infinity, and then run BFS from every land cell and calculate the shortest distance to each water cell, and update the minDistance[][] to the minimum shortest distance to a water cell. The maximum value which is not equal to infinity, of the water cell in minDistance[][] will be our ans.

The algorithm is as follows:

• Declare an ans variable and set it to -1, representing the largest distance of a land cell from the nearest water cell.
• Declare a dx array representing and set it to {1, 0, -1, 0}, representing the directions of all four neighboring cells.
• Declare a dy array representing and set it to {0, 1, 0, -1}, representing the directions of all four neighboring cells.
• Declare a 2D array minDistance[][] with N rows and N columns and set it to infinity, where minDistance[i][j] represents the minimum possible distance between a water cell from a land cell.
• Iterate from i = 0 to N,
• Iterate from j = 0 to N,
• If ARR[i][j] == 1,
• Run BFS from this land cell.
• Compute the shortest distance from this land cell to every reachable water cell and store it to a matrix distance[][].
• update the minDistance[][],
• Set minDistance[i][j] = min(minDistance[i][j], distance[i][j]).
• Iterate from i = 0 to N,
• Iterate from j = 0 to N,
• If ARR[i][j] == 0 and minDistance[i][j] < infinity,
• Update ans to max(ans, minDistance[i][j]).
• Return the ans.