LeetCode 1162. 地图分析

Categories:

题目描述
思路分析
1. 解法一：多源 BFS（推荐）
相似题目

题目描述

✅ 1162. 地图分析

思路分析

解法一：多源 BFS（推荐）

核心思路：

将所有陆地同时入队，作为 BFS 多源起点。

按层扩展到水域，最后一层的距离即为最大距离。

若全为陆地或全为水域，返回 -1。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示网格边长。

空间复杂度：O(n^2)，用于队列与访问标记。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean hasLand = false;
        boolean hasWater = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    hasLand = true;
                } else {
                    hasWater = true;
                }
            }
        }

        if (!hasLand || !hasWater) {
            return -1;
        }

        int dist = -1;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        while (!queue.isEmpty()) {
            int size = queue.size();
            dist++;
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int nr = cur[0] + dr[k];
                    int nc = cur[1] + dc[k];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] == 1) {
                        continue;
                    }
                    grid[nr][nc] = 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }
}

func maxDistance(grid [][]int) int {
	n := len(grid)
	queue := make([][2]int, 0)
	hasLand := false
	hasWater := false

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				queue = append(queue, [2]int{i, j})
				hasLand = true
			} else {
				hasWater = true
			}
		}
	}

	if !hasLand || !hasWater {
		return -1
	}

	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	dist := -1
	for len(queue) > 0 {
		size := len(queue)
		dist++
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			for _, d := range dirs {
				nr := cur[0] + d[0]
				nc := cur[1] + d[1]
				if nr < 0 || nr >= n || nc < 0 || nc >= n {
					continue
				}
				if grid[nr][nc] == 1 {
					continue
				}
				grid[nr][nc] = 1
				queue = append(queue, [2]int{nr, nc})
			}
		}
	}

	return dist
}

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	BFS
542. 01 矩阵	中等	多源 BFS
994. 腐烂的橘子	中等	BFS
934. 最短的桥	中等	BFS
200. 岛屿数量	中等	BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/52002973