算法题/网格的BFS：离开陆地的最远距离

题目

有一个NxN的网格grid，上面的每个网格都用0和1标记好了。其中0代表海洋，1代表陆地。请在其中找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。 距离是指曼哈顿距离，即(x0, y0)和(x1, y1)这两个单元格之间的距离是|x0-x1|+|y0-y1|。

示例1：

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：海洋单元格(1,1)和所有陆地单元格之间的距离都达到最大，最大距离为2。

解答

Java

public class Solution{
    public int maxDistance(int[][] grid) {
        int N = grid.length;

        Queue<int[]> queue = new ArrayDeque<>();
        // 将所有的陆地格子加入队列
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        // 如果地图上只有陆地或者海洋，返回 -1
        if (queue.isEmpty() || queue.size() == N * N) {
            return -1;
        }

        int[][] moves = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        };

        int distance = -1; // 记录当前遍历的层数（距离）
        while (!queue.isEmpty()) {
            distance++;
            int n = queue.size();
            for (int i = 0; i < n; i++) { 
                int[] node = queue.poll();
                int r = node[0];
                int c = node[1];
                for (int[] move : moves) {
                    int r2 = r + move[0];
                    int c2 = c + move[1];
                    if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
                        // 将已经遍历过的格子标记为2
                        grid[r2][c2] = 2;
                        queue.add(new int[]{r2, c2});
                    }
                }
            }
        }

        return distance;
    }

    // 判断坐标 (r, c) 是否在网格中
    boolean inArea(int[][] grid, int r, int c) {
        return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
    }
}

JavaScript

class Solution {
  maxDistance(grid) {
    const N = grid.length;
  
    const queue = [];
    // 将所有的陆地格子加入队列
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (grid[i][j] === 1) {
          queue.push([i, j]);
        }
      }
    }
  
    // 如果地图上只有陆地或者海洋，返回 -1
    if (queue.length === 0 || queue.length === N * N) {
      return -1;
    }
  
    const moves = [
      [-1, 0], [1, 0], [0, -1], [0, 1]
    ];
  
    let distance = -1; // 记录当前遍历的层数（距离）
    while (queue.length > 0) {
      distance++;
      const n = queue.length;
      for (let i = 0; i < n; i++) {
        const node = queue.shift();
        const r = node[0];
        const c = node[1];
        for (const move of moves) {
          const r2 = r + move[0];
          const c2 = c + move[1];
          if (this.inArea(grid, r2, c2) && grid[r2][c2] === 0) {
            // 将已经遍历过的格子标记为2
            grid[r2][c2] = 2;
            queue.push([r2, c2]);
          }
        }
      }
    }
  
    return distance;
  }
  
  // 判断坐标 (r, c) 是否在网格中
  inArea(grid, r, c) {
    return (
      0 <= r && r < grid.length &&
      0 <= c && c < grid[0].length
    );
  }
}

Python

from typing import List
from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        queue = deque()
        # 将所有的陆地格子加入队列
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 1:
                    queue.append([i, j])
        
        # 如果地图上只有陆地或者海洋，返回 -1
        if len(queue) == 0 or len(queue) == N * N:
            return -1
        
        moves = [
            [-1, 0], [1, 0], [0, -1], [0, 1]
        ]
        
        distance = -1  # 记录当前遍历的层数（距离）
        while queue:
            distance += 1
            n = len(queue)
            for _ in range(n):
                node = queue.popleft()
                r = node[0]
                c = node[1]
                for move in moves:
                    r2 = r + move[0]
                    c2 = c + move[1]
                    if self.inArea(grid, r2, c2) and grid[r2][c2] == 0:
                        # 将已经遍历过的格子标记为2
                        grid[r2][c2] = 2
                        queue.append([r2, c2])
        
        return distance
    
    # 判断坐标 (r, c) 是否在网格中
    def inArea(self, grid: List[List[int]], r: int, c: int) -> bool:
        return 0 <= r < len(grid) and 0 <= c < len(grid[0])

Go

package main

import (
	"fmt"
)

type Solution struct{}

func (s *Solution) maxDistance(grid [][]int) int {
	N := len(grid)

	queue := [][]int{}
	// 将所有的陆地格子加入队列
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			if grid[i][j] == 1 {
				queue = append(queue, []int{i, j})
			}
		}
	}

	// 如果地图上只有陆地或者海洋，返回 -1
	if len(queue) == 0 || len(queue) == N*N {
		return -1
	}

	moves := [][]int{
		{-1, 0}, {1, 0}, {0, -1}, {0, 1},
	}

	distance := -1 // 记录当前遍历的层数（距离）
	for len(queue) > 0 {
		distance++
		n := len(queue)
		for i := 0; i < n; i++ {
			node := queue[0]
			queue = queue[1:]
			r := node[0]
			c := node[1]
			for _, move := range moves {
				r2 := r + move[0]
				c2 := c + move[1]
				if s.inArea(grid, r2, c2) && grid[r2][c2] == 0 {
					// 将已经遍历过的格子标记为2
					grid[r2][c2] = 2
					queue = append(queue, []int{r2, c2})
				}
			}
		}
	}

	return distance
}

// 判断坐标 (r, c) 是否在网格中
func (s *Solution) inArea(grid [][]int, r, c int) bool {
	return r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0])
}

func main() {
	solution := &Solution{}

	grid := [][]int{
		{1, 0, 1},
		{0, 0, 0},
		{1, 0, 1},
	}

	maxDist := solution.maxDistance(grid)
	fmt.Println("Maximum distance:", maxDist)
}