5 Best Ways to Find Land with Longest Distance from Water in Python

Rate this post

πŸ’‘ Problem Formulation: The goal is to create Python programs that can find the point on land that is the furthest distance from any body of water, such as lakes or oceans. This might involve a grid-based map where land and water are marked by different values, and we seek the land point with maximum distance from any water point. For example, given a 2D matrix representing a map, where 0s represent water and 1s represent land, the expected output is the coordinates of the land point that is furthest from water.

Method 1: Breadth-First Search (BFS)

This method employs the Breadth-First Search algorithm, starting from each water cell and moving outward to calculate the distance to the nearest water cell for each land cell. This method is thorough and guarantees the longest distance will be found. It uses a queue to systematically visit cells in increasing distance from water, updating distances for land cells.

Here’s an example:

from collections import deque

def max_distance(grid):
    rows, cols = len(grid), len(grid[0])
    water_cells = deque([(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 0])
    if not water_cells or len(water_cells) == rows * cols:
        return -1

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    max_dist = -1
    
    while water_cells:
        r, c = water_cells.popleft()
        for dr, dc in directions:   
            nr, nc = r + dr, c + dc
   
            if 0 <=nr< rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = grid[r][c] + 1
                max_dist = max(max_dist, grid[nr][nc])
                water_cells.append((nr, nc))
                
    return max_dist - 1

# Example grid
grid = [
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 1],
    [1, 0, 0, 1, 1],
    [1, 1, 1, 1, 1]
]
print(max_distance(grid))

The output of this code snippet will be:

2

In the provided example, the function defines the grid with land and water, then calculates the maximum distance of any land cell from water. It initiates a BFS from water cells and propagates distance information until all land cells have been reached, returning the highest value minus 1, because the first increment represents the bordering land cells right next to water.

Method 2: Dynamic Programming

Dynamic Programming can be used to solve this problem by iterating through the grid twice: once from top-left to bottom-right, and then from bottom-right to top-left. This ensures that each cell contains the distance to the nearest water cell considering all four directions. It efficiently calculates the distances by building them up from previously calculated values.

Here’s an example:

def max_distance(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[float('inf') if grid[r][c] else 0 for c in range(cols)] for r in range(rows)]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c]:
                if r > 0:
                    dp[r][c] = min(dp[r][c], dp[r-1][c] + 1)
                if c > 0:
                    dp[r][c] = min(dp[r][c], dp[r][c-1] + 1)

    for r in reversed(range(rows)):
        for c in reversed(range(cols)):
            if grid[r][c]:
                if r < rows - 1:
                    dp[r][c] = min(dp[r][c], dp[r+1][c] + 1)
                if c < cols - 1:
                    dp[r][c] = min(dp[r][c], dp[r][c+1] + 1)

    max_dist = max(max(val for val in row if val != float('inf')) for row in dp)
    return max_dist if max_dist != float('inf') else -1

# Example grid
grid = [
    [1, 1, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1]
]
print(max_distance(grid))

The output of this code snippet will be:

2

Here, the algorithm initializes a distance matrix ‘dp’ where water cells are set to 0 and land cells to infinity. Then it iterates over the matrix in both directions to calculate minimum distances. The final maximum value is computed excluding infinite values to get the maximum distance from water.

Method 3: Multi-source BFS

Multi-source BFS is similar to the standard BFS but begins the search from multiple sources simultaneously. For this problem, water cells act as sources. This method is especially efficient if there are multiple water cells, as it spreads out from all water sources together rather than one at a time.

Here’s an example: