# Solution For As Far From Land As Possible

As Far From Land As Possible is a question on LeetCode, which is a platform that provides coding challenges to software developers. The problem statement is quite straightforward:

Given an n x n grid containing only 0s and 1s, where 0 represents water and 1 represents land, find the distance of the nearest land cell from each water cell. The distance between two adjacent land cells is 1 unit. You can assume that there is at least one land cell.

In other words, we need to find the distance of the nearest land cell for each water cell. We can use breadth-first search (BFS) to solve this problem efficiently.

Here’s the step-by-step solution to this problem:

Step 1: Create a queue to store the position of all the water cells in the grid.

Step 2: Initialize a visited matrix of the same size as the grid and mark all the land cells as visited.

Step 3: For all the water cells in the queue, perform a BFS operation and find the distance to each land cell. We start from each water cell and visit all its neighbors (up, down, left, right) one by one. If a neighbor cell is a land cell, we mark it as visited, and the distance to it is 1. If a neighbor cell is a water cell and not yet visited, we mark it as visited and add it to the queue along with its distance.

Step 4: Repeat step 3 until the queue becomes empty. At the end of each BFS operation, we update the minimum distance from the water cell to any land cell.

Step 5: Once all the BFS operations are complete, return the maximum distance found in the visited matrix. The result will be the answer to the problem.

Here’s the Python code for the same:

```from collections import deque def maxDistance(grid): q = deque([]) visited = [[0 for j in range(len(grid))] for i in range(len(grid))] # loop through the grid, starting from every land cells for i in range(len(grid)): for j in range(len(grid)): if grid[i][j] == 1: visited[i][j] = 1 q.append((i,j,0)) # handle case if there were no land cells if not q or len(q) == len(grid)**2: return -1 # perform BFS while q: i, j, dis = q.popleft() # check all neighbors of current cell for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: if x<0 or y<0 or x>=len(grid) or y>=len(grid): continue if not visited[x][y]: visited[x][y] = 1 q.append((x,y,dis+1)) # update the grid with the distance to the nearest land grid[x][y] = min(grid[x][y], dis+1) # find the maximum distance maxDis = 0 for i in range(len(grid)): for j in range(len(grid)): # if there is a water cell if grid[i][j] == 0: maxDis = max(maxDis, visited[i][j]) return maxDis```

This solution has a time complexity of O(n^2), where n is the size of the grid.

Overall, this is an effective solution to the As Far From Land As Possible problem on LeetCode.

## Step by Step Implementation For As Far From Land As Possible

```class Solution {
public int maxDistance(int[][] grid) {
//BFS
//We will keep track of all the land cells in a queue
//We will iterate over the whole grid and if we encounter a water cell, we will check it's distance from all it's adjacent land cells
//We will keep track of the max distance and return it at the end

int maxDistance = -1;
int n = grid.length;
int m = grid[0].length;

for(int i=0; i= 0 && newR < n && newC >= 0 && newC < m && grid[newR][newC] == 0){
grid[newR][newC] = grid[r][c] + 1;
}
}
}
}

for(int i=0; i 1){
maxDistance = Math.max(maxDistance, grid[i][j] - 1);
}
}
}

return maxDistance;

}
}```
```from collections import deque

class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
# BFS
# initialize a queue and add all the land cells to it
# iterate over the queue and for each land cell, check its neighbors
# if any of the neighbors is water, add it to the queue and update its distance
# return the maximum distance

# corner case
if not grid or not grid[0]:
return -1

# initialize a queue and add all the land cells to it
queue = deque()
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
queue.append((i, j))

# iterate over the queue and for each land cell, check its neighbors
# if any of the neighbors is water, add it to the queue and update its distance
# return the maximum distance
max_dist = 0
while queue:
i, j = queue.popleft()
for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
grid[x][y] = grid[i][j] + 1
max_dist = max(max_dist, grid[x][y])
queue.append((x, y))

return -1 if max_dist == 0 else max_dist - 1```
```var asFarFromLandAsPossible = function(grid) {

// create a queue for BFS
let queue = [];

// create a visited matrix
let visited = [];
for (let i = 0; i < grid.length; i++) {
visited.push([]);
for (let j = 0; j < grid[0].length; j++) {
visited[i].push(false);
}
}

// get all the land cells and push them into the queue
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
queue.push([i, j]);
visited[i][j] = true;
}
}
}

// BFS
let level = 0;
let curr;
while (queue.length > 0) {
let size = queue.length;
for (let i = 0; i < size; i++) {
curr = queue.shift();
let currX = curr[0];
let currY = curr[1];

// check all 4 directions
if (currX > 0 && visited[currX - 1][currY] === false) {
queue.push([currX - 1, currY]);
visited[currX - 1][currY] = true;
}
if (currX < grid.length - 1 && visited[currX + 1][currY] === false) {
queue.push([currX + 1, currY]);
visited[currX + 1][currY] = true;
}
if (currY > 0 && visited[currX][currY - 1] === false) {
queue.push([currX, currY - 1]);
visited[currX][currY - 1] = true;
}
if (currY < grid[0].length - 1 && visited[currX][currY + 1] === false) {
queue.push([currX, currY + 1]);
visited[currX][currY + 1] = true;
}
}
level++;
}

return level - 1;
};```
```The problem is as follows:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution {
public:
int maxDistance(vector>& grid) {
int n = grid.size(), m = grid[0].size();
int ans = -1;
queue> q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 1) {
q.push({i, j});
}
}
}
vector dx = {0, 0, 1, -1};
vector dy = {1, -1, 0, 0};
while(!q.empty()) {
int size = q.size();
while(size--) {
auto [x, y] = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0) {
grid[nx][ny] = 1;
q.push({nx, ny});
}
}
}
ans++;
}
return ans == 0 ? -1 : ans - 1;
}
};```
```using System;

class GFG {

// Function to find the maximum
// distance from any cell
static int findMaxDistance(int[,] mat,
int n, int m)
{

// To store maximum distance
// from a land cell
int result = -1;

// To store land cells
// in a queue
Queue Q = new Queue();

// To store visited cells
bool[,] visited = new bool[n, m];

// Loop over each cell
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{

// If current cell is a water
// cell, continue
if (mat[i, j] == 0 || visited[i, j])
continue;

// the queue
Q.Enqueue(new Pair(i, j));

// Distance of current cell
// from the starting cell
int dist = 0;

// Do BFS starting from
// current cell
while (Q.Count != 0)
{

// Remove front item
// from the queue
Pair p = Q.Dequeue();

// Get i and j coordinates
// of the current cell
int x = p.x;
int y = p.y;

// If this is the starting
// cell, continue
if (x == i && y == j)
continue;

// If this has already been
// visited, continue
if (visited[x, y])
continue;

// Mark this cell as visited
visited[x, y] = true;

// Update result
result = Math.Max(result, dist);

// Loop over all 8 possible
// moves from current cell
for (int row = x - 1; row <= x + 1; row++)
{
for (int col = y - 1; col <= y + 1; col++)
{

// If row number and column
// number are valid and
// current cell is not a
// water cell and not
// visited yet
if (isValid(mat, row, col,
n, m) &&
mat[row, col] == 1 &&
!visited[row, col])
{

// enqueue newly found
// water cell
Q.Enqueue(new Pair(row, col));

// Increment distance
// by 1
dist++;
}
}
}
}
}
}
return result;
}

// Utility method to check if given
// row and column are valid or not
static bool isValid(int[,] mat, int row,
int col, int n, int m)
{
if (row >= 0 && row < n &&
col >= 0 && col < m)
return true;
return false;
}

// Driver code
public static void Main()
{
int n = 5, m = 5;

int[,] mat = {{ 1, 0, 1, 0, 1 },
{ 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }};

Console.Write("Maximum distance " +
"from a land cell is " +
findMaxDistance(mat, n, m));
}
}

// Class to store row and column
// of a cell
class Pair
{
public int x, y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]