【Day 51 】2022-12-21 - 1162. 地图分析

[azl397985856]

1162. 地图分析

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/as-far-from-land-as-possible/

前置知识

暂无

题目描述

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。
其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，
这个海洋单元格到离它最近的陆地单元格的距离是最大的。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

如果网格上只有陆地或者海洋，请返回 -1。

 

示例 1：

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

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

提示：

1 <= grid.length == grid[0].length <= 100
grid[i][j] 不是 0 就是 1

[whoam-challenge]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0])

    stack = []
    for i in range(m):
        for j in range(n):
            if grid[i][j]:
                stack.append([i, j])

    if len(stack) == m*n or not stack:
        return -1

    step = 1
    while stack:
        nex = []
        for i, j in stack:
            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 not grid[x][y]:
                    nex.append([x, y])
                    grid[x][y] = step
        stack = nex
        step += 1
    return step-2

[snmyj]

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for(int x = 0; x < m; ++x){
            if(grid[x][0] == 1){
                dfs(grid, x, 0);
            }

            if(grid[x][n - 1] == 1){
                dfs(grid, x, n - 1);
            }
        }

        for(int y = 0; y < n; ++y){
            if(grid[0][y] == 1){
                dfs(grid, 0, y);
            }

            if(grid[m - 1][y] == 1){
                dfs(grid, m - 1, y);
            }
        }

        int count = 0;
        for(int x = 0; x < m; ++x){
            for(int y = 0; y < n; ++y){
                if(grid[x][y] == 1){
                    ++count;
                }
            }
        }

        return count;
    }

    private void dfs(int[][] grid, int x, int y){

        if(x >= grid.length || x < 0 || y >= grid[0].length || y < 0 || grid[x][y] == 0){
            return;
        }

        grid[x][y] = 0;

        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}

[buer1121]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int:

    n = len(grid)
    steps = -1
    queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]

    if len(queue) == 0 or len(queue) == n ** 2: return steps

    while len(queue) > 0:
        for _ in range(len(queue)): 
            x, y = queue.pop(0)
            for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:
                    queue.append((xi, yj))
                    grid[xi][yj] = -1
        steps += 1

    return steps

[ringo1597]

代码

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    int n;
    int[][] grid;

    public int maxDistance(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, findNearestLand(i, j));
                }
            }
        }
        return ans;
    }

    public int findNearestLand(int x, int y) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{x, y, 0});
        vis[x][y] = true;
        while (!queue.isEmpty()) {
            int[] f = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int nx = f[0] + dx[i], ny = f[1] + dy[i];
                if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {
                    continue;
                }
                if (!vis[nx][ny]) {
                    queue.offer(new int[]{nx, ny, f[2] + 1});
                    vis[nx][ny] = true;
                    if (grid[nx][ny] == 1) {
                        return f[2] + 1;
                    }
                }
            }
        }
        return -1;
    }
}

[zjsuper]

class Solution:

tle

def maxDistance(self, grid: List[List[int]]) -> int:
    ans = -1
    n = len(grid)
    que = collections.deque([(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1])
    if len(que) == 0 or len(que) == n ** 2: return -1
    def bfs(start):
        r,c = start
        queue = collections.deque([(r,c)])
        count = 0
        while queue:
            count+=1
            for _ in range(len(queue)):
                a,b = queue.popleft()
                for i,j in [(a+1,b),(a-1,b),(a,b+1),(a,b-1)]:
                    if i<len(grid) and i>-1 and j<len(grid[0]) and j>-1:
                        if grid[i][j] == 1:
                            return count 
                        else:
                            queue.append((i,j))

        return -1

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 0:
                ans = max(ans,bfs((i,j)))
    return ans

[arinzz]

class Solution { public: int maxDistance(vector<vector>& grid) { const int M = grid.size(); const int N = grid[0].size();

    deque<pair<int, int>> deq;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (grid[i][j] == 1) {

                deq.push_back({i, j});
            }
        }
    }

    if (deq.size() == 0 || deq.size() == M * N) {
        return -1;
    }

    int distance = -1;

    while (deq.size() != 0) {

        distance ++;

        int size = deq.size();
        while (size --) {

            auto cur = deq.front(); deq.pop_front();

            for (auto& d : directions) {
                int x = cur.first + d[0];
                int y = cur.second + d[1];

                if (x < 0 || x >= M || y < 0 || y >= N ||
                    grid[x][y] != 0) {
                    continue;
                }

                deq.push_back({x, y});
            }
        }
    }

    return distance;
}

private: vector<vector> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; };

[Ryanbaiyansong]

··· class Solution: def maxDistance(self, a: List[List[int]]) -> int: n = len(a) q = deque() for i, l in enumerate(a): for j, x in enumerate(l): if x: q.append((i,j))

    if len(q) == n * n or len(q) == 0: 
        return -1

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    steps = 0
    while q:
        sz = len(q)
        for _ in range(sz):
            x, y = q.popleft()
            for dx, dy in dirs:
                nx, ny = dx + x, dy + y
                if 0 <= nx < n and \
                   0 <= ny < n and \
                   a[nx][ny] == 0:
                   a[nx][ny] = 1
                   q.append((nx, ny))
        steps += 1

    return steps - 1

···

[Alyenor]

function maxDistance(grid: number[][]): number {
  const dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1]
  let g = grid, n = g.length
  let q = []
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (g[i][j]) {
        q.push([i, j])
      }
    }
  }
  if (q.length === 0 || q.length === n * n) {
    return -1;
  }
  let t: number[] = [];
  while (q.length > 0) {
    t = q.shift()!
    for (let i = 0; i < 4; i++) {
      const x = dx[i] + t[0], y = dy[i] + t[1]
      if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] !== 0) continue
      g[x][y] = g[t[0]][t[1]] + 1
      q.push([x, y])
    }
  }
  return g[t[0]][t[1]] - 1
};

[mayloveless]

思路

参考官方题解。计算每个格子到陆地的距离，最后从水域格子里选取最大的到陆地的距离

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    const h = grid.length
    const w = grid[0].length

    const arr = [];
    // 记录到陆地的距离
    const dp = Array(h).fill().map(() => Array(w).fill(Infinity))
    for (let i = 0; i < h; ++i) {
        for (let j = 0; j < w; ++j) {
            if (grid[i][j] == 1) {
                arr.push([i, j]);
                dp[i][j] = 0;// 陆地到陆地距离为0
            }  
        }
    }

     while (arr.length) {
        const value = arr.pop()
        let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]// 试探
        for (let k = 0; k < 4; ++k) {
            let newi = value[0] + directions[k][0]
            let newj = value[1] + directions[k][1]
            if (newi >= 0 && newi < h && newj >= 0 && newj < w
                && dp[newi][newj] > dp[value[0]][value[1]] + 1) {// 没有访问过，加入队列
               dp[newi][newj] = dp[value[0]][value[1]] + 1; // 访问过了，+1：水域
               arr.push([newi,newj]);
            }
        }
    }

    let res = -1;
    for (let i = 0; i < h; ++i) {
        for (let j = 0; j < w; ++j) {
            if (grid[i][j] == 0 && dp[i][j] !== Infinity) { // 水域到陆地
               res = Math.max(res, dp[i][j]);
            }
        }
    }
    return res;
};

复杂度

时间O(n^2) 空间O （N^2）

[Abby-xu]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: dist = [[float('inf') for in grid[0]] for in grid] for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: dist[i][j] = 0 continue if i-1 >= 0: dist[i][j] = min(dist[i-1][j]+1, dist[i][j]) if j-1 >= 0: dist[i][j] = min(dist[i][j-1]+1, dist[i][j]) maxer = -1 for i in range(len(grid)-1, -1, -1): for j in range(len(grid[0])-1, -1, -1): if grid[i][j] == 1: dist[i][j] = 0 continue if i+1 < len(grid): dist[i][j] = min(dist[i+1][j]+1, dist[i][j]) if j+1 < len(grid[0]): dist[i][j] = min(dist[i][j+1]+1, dist[i][j]) maxer = max(maxer, dist[i][j]) if maxer == float('inf'): return -1 return maxer

[RestlessBreeze]

代码

class Solution {
public:
    static constexpr int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    static constexpr int MAX_N = 100 + 5;

    struct Coordinate {
        int x, y, step;
    };

    int n, m;
    vector<vector<int>> a;

    bool vis[MAX_N][MAX_N];

    int findNearestLand(int x, int y) {
        memset(vis, 0, sizeof vis);
        queue <Coordinate> q;
        q.push({x, y, 0});
        vis[x][y] = 1;
        while (!q.empty()) {
            auto f = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = f.x + dx[i], ny = f.y + dy[i];
                if (!(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= m - 1)) {
                    continue;
                }
                if (!vis[nx][ny]) {
                    q.push({nx, ny, f.step + 1});
                    vis[nx][ny] = 1;
                    if (a[nx][ny]) {
                        return f.step + 1;
                    }
                }
            }
        }
        return -1;
    }

    int maxDistance(vector<vector<int>>& grid) {
        this->n = grid.size();
        this->m = grid.at(0).size();
        a = grid;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!a[i][j]) {
                    ans = max(ans, findNearestLand(i, j));
                }
            }
        }
        return ans;
    }
};

[testplm]

from collections import deque

class Solution:
    def is_cell_valid(self, cell_i, cell_j, n):
        return (cell_i >= 0 and cell_i <= n - 1) and (cell_j >= 0 and cell_j <= n-1)

    def add_adj_to_search(self, cell_i, cell_j, queue, n):
        if self.is_cell_valid(cell_i, cell_j, n):
            queue.append((cell_i, cell_j, 1))

    def maxDistance(self, grid):
        n = len(grid)
        dis = [[-1 for _ in range(n) ]for _ in range(n)]
        q = deque()
        lands = []
        furthest_seen = 1

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dis[i][j] = 0
                    lands.append((i, j))

        if not lands or len(lands) == n**2:
            return -1

        cell_neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for land_i, land_j in lands:
            for cell_i, cell_j in cell_neighbors:
                self.add_adj_to_search(land_i + cell_i, land_j + cell_j, q, n)

        while q:
            cell_i, cell_j, distance = q.popleft()
            if dis[cell_i][cell_j] == -1:

                dis[cell_i][cell_j] = distance
                furthest_seen = max(furthest_seen, distance)

                for nei_i, nei_j in cell_neighbors:
                    new_i, new_j = cell_i + nei_i, cell_j + nei_j

                    if self.is_cell_valid(new_i, new_j, n):
                        q.append((new_i, new_j, distance + 1))

        return furthest_seen

[liuajingliu]

/**

• @param {number[][]} grid
• @return {number} */ var maxDistance = function (grid) { let n = grid.length; let queue = [], areaCount = 0; // 0 海洋 1陆地 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // 所有陆地入队列 if (grid[i][j] == 1) queue.push([i, j]); // 统计海洋的数量 else areaCount++; } } // 只有陆地或者说只有海洋 if (queue.length == 0 || areaCount == 0) return -1; let directions = [ [0, 1], [0, -1], [-1, 0], [1, 0], ]; // 广度扩散 let depth = 0; while (queue.length) { let size = queue.length; depth++; for (let i = 0; i < size; i++) { // 队首出 let [curI, curJ] = queue.shift(); for (let dir of directions) { let newI = dir[0] + curI, newJ = dir[1] + curJ; // 越界 或者已经是陆地了 if ( newI < 0 || newJ < 0 || newI >= n || newJ >= n || grid[newI][newJ] == 1 ) continue; // 把所有的海洋都变成陆地 grid[newI][newJ] = 1; queue.push([newI, newJ]); areaCount--; // 如果海洋都变成了陆地，就是走过的最远路径了 if (areaCount == 0) return depth; } } } return -1; };

[liuajingliu]

/**

@param {number[][]} grid
@return {number}
*/
var maxDistance = function (grid) {
    let n = grid.length;
    let queue = [],
    areaCount = 0;
    // 0 海洋 1陆地
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        // 所有陆地入队列
        if (grid[i][j] == 1)            queue.push([i, j]);
        // 统计海洋的数量
        else areaCount++;
        }
    }
    // 只有陆地或者说只有海洋
    if (queue.length == 0 || areaCount == 0) return -1;
    let directions = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0],
    ];
    // 广度扩散
    let depth = 0;
    while (queue.length) {
        let size = queue.length;
        depth++;
        for (let i = 0; i < size; i++) {
            // 队首出
            let [curI, curJ] = queue.shift();
            for (let dir of directions) {
                let newI = dir[0] + curI,
                newJ = dir[1] + curJ;
                // 越界 或者已经是陆地了
                if (
                newI < 0 ||
                newJ < 0 ||
                newI >= n ||
                newJ >= n ||
                grid[newI][newJ] == 1
                )
                continue;
                // 把所有的海洋都变成陆地
                grid[newI][newJ] = 1;
                queue.push([newI, newJ]);
                areaCount--;
                // 如果海洋都变成了陆地，就是走过的最远路径了
                if (areaCount == 0) return depth;
            }
        }
    }
    return -1;
};

[chiehw]

// BFS：超时
int MATRIX_X[] = {1, 0, -1, 0};
int MATRIX_Y[] = {0, -1, 0, 1};
const int MATRIX_LEN = 4;
const int MAX_N = 100 + 5;

struct Point{
    int x;
    int y;
    int len;
    Point(int x, int y, int len): x(x), y(y), len(len) {}
};

bool visited[MAX_N][MAX_N];

#define ADD_ACCESS_FLAG(point) visited[point.x][point.y] = true
#define INIT_VISITED(value) memset(visited, value, sizeof(visited))
#define HAS_VISITED(point) visited[point.x][point.y] == true

class Solution {
private:
    static bool is_in_grid(const vector<vector<int>> &grid, Point point){
        return point.x >= 0 && point.y >=0 && point.x < grid.size() && point.y < grid[0].size();
    }

    static bool is_ocean(const vector<vector<int>> &grid, Point point){
        return grid[point.x][point.y] == 0;
    }

    void add_around_point_to_queue(queue<Point> &q, Point point, const vector<vector<int>> &grid){
        for(int i=0; i<MATRIX_LEN; i++){
            Point nextPoint = Point(point.x + MATRIX_X[i], point.y + MATRIX_Y[i], point.len + 1);
            if(is_in_grid(grid, nextPoint) && !HAS_VISITED(nextPoint)){
                ADD_ACCESS_FLAG(nextPoint);
                q.push(nextPoint);
            }
        }
    }

    int bfs(vector<vector<int>> &grid, Point startPoint){
        INIT_VISITED(0);
        ADD_ACCESS_FLAG(startPoint);
        queue<Point> q;
        q.push(startPoint);
        int ans=-1;

        while(!q.empty()){
            Point point = q.front();
            q.pop();

            if(!is_in_grid(grid, point)){
                continue;
            }

            if(is_ocean(grid, point)){
                add_around_point_to_queue(q, point, grid);
            }else{
                ans = point.len;
                break;
            }
        }
        return ans;
    }
public:
    int maxDistance(vector<vector<int>>& grid) {
        int size = grid.size();
        int x, y;
        int ans=-1;

        for(x=0; x<size; x++){
            for(y=0; y<size; y++){
                Point point = Point(x, y, 0);

                if(is_ocean(grid, point)){
                    int len = bfs(grid, point);
                    if(len > ans){
                        ans = len;
                    }
                }
            }
        }

        return ans;
    }
};

[AtaraxyAdong]

class Solution {
    int[][] grid;
    int[] x = {-1, 0, 1, 0};
    int[] y = {0, -1, 0, 1};
    int n;

    public int maxDistance(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int maxManhattanDistance = -1;

        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid.length; column++) {

                if (grid[row][column] == 0) {
                    maxManhattanDistance = Math.max(maxManhattanDistance, detectDistance(row, column));
                }

            }

        }
        return maxManhattanDistance;
    }

    private int detectDistance(int row, int column) {

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] searched = new boolean[n][n];

        queue.offer(new int[]{row, column, 0});
        searched[row][column] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            // 然后遍历四个方向 左下右上 四个子节点
            for (int i = 0; i < 4; i++) {
                int detectX = poll[0] + x[i];
                int detectY = poll[1] + y[i];
                if (detectX < 0 || detectX >= grid.length || detectY < 0 || detectY >= grid.length) {
                    continue;
                }
                // 这次bfs中没有遍历到这个点
                if (!searched[detectX][detectY]) {
                    // 先把其子节点加入到队列中
                    queue.offer(new int[]{detectX, detectY, poll[2] + 1});
                    // 标记已经遍历过这个点了
                    searched[detectX][detectY] = true;
                    // 找到了土地 返回此时的距离
                    if (grid[detectX][detectY] == 1) {
                        return poll[2] + 1;
                    }
                }
            }
        }

        return -1;
    }

}

[Alexno1no2]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        steps = -1
        q = deque([(i, j) for i in range(N) for j in range(N) if grid[i][j] == 1])
        if len(q) == 0 or len(q) == N ** 2:
            return steps
        move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while len(q) > 0:
            for _ in range(len(q)):
                x, y = q.popleft()
                for dx, dy in move:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < N and 0 <= ny < N and grid[nx][ny] == 0:
                        q.append((nx, ny))
                        grid[nx][ny] = -1
            steps += 1

        return steps

[klspta]

思路

宽度优先遍历 先将所有陆地入队，然后一圈一圈的遍历，同时记录每一次遍历的点，最后一个遍历到的点就是最远的海洋，并且一定是最近的陆地扩散到的。

class Solution {
    public int maxDistance(int[][] grid) {

        int[] dx = new int[] {1, 0, -1, 0};
        int[] dy = new int[] {0, 1, 0, -1};

        Queue<int[]> queue = new ArrayDeque<>();
        int m = grid.length;
        int n = grid[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int[] point = null;
        boolean hasOcean = false;
        while(!queue.isEmpty()){
            point = queue.poll();
            int x = point[0];
            int y = point[1];
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != 0){
                    continue;
                }
                grid[nx][ny] = grid[x][y] + 1;
                hasOcean = true;
                queue.offer(new int[]{nx, ny});
            }
        }

        if(point == null || !hasOcean){
            return -1;
        }

        return grid[point[0]][point[1]] - 1;

    }
}

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxDistance(int[][] grid) {
int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Queue<int[]> queue = new ArrayDeque<>();
        int m = grid.length, n = grid[0].length;
        // 先把所有的陆地都入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[] {i, j});
                }
            }
        }

        // 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋
        boolean hasOcean = false;
        int[] point = null;
        while (!queue.isEmpty()) {
            point = queue.poll();
            int x = point[0], y = point[1];
            // 取出队列的元素，将其四周的海洋入队。
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
                    continue;
                }
                grid[newX][newY] = grid[x][y] + 1; 
                hasOcean = true;
                queue.offer(new int[] {newX, newY});
            }
        }

        // 没有陆地或者没有海洋，返回-1。
        if (point == null || !hasOcean) {
            return -1;
        }

        // 返回最后一次遍历到的海洋的距离。
        return grid[point[0]][point[1]] - 1;

    }
}

[AstrKing]

思路

广度优先算法，算出每一个海洋区域的最近陆地区域，然后记录下它们的距离，然后在这些距离里面取一个最大值。

代码

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    int n;
    int[][] grid;

    public int maxDistance(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, findNearestLand(i, j));
                }
            }
        }
        return ans;
    }

    public int findNearestLand(int x, int y) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{x, y, 0});
        vis[x][y] = true;
        while (!queue.isEmpty()) {
            int[] f = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int nx = f[0] + dx[i], ny = f[1] + dy[i];
                if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {
                    continue;
                }
                if (!vis[nx][ny]) {
                    queue.offer(new int[]{nx, ny, f[2] + 1});
                    vis[nx][ny] = true;
                    if (grid[nx][ny] == 1) {
                        return f[2] + 1;
                    }
                }
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度：O(n4)

空间复杂度：O(n2)

[zywang0]

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    int n;
    int[][] grid;

    public int maxDistance(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, findNearestLand(i, j));
                }
            }
        }
        return ans;
    }

    public int findNearestLand(int x, int y) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{x, y, 0});
        vis[x][y] = true;
        while (!queue.isEmpty()) {
            int[] f = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int nx = f[0] + dx[i], ny = f[1] + dy[i];
                if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {
                    continue;
                }
                if (!vis[nx][ny]) {
                    queue.offer(new int[]{nx, ny, f[2] + 1});
                    vis[nx][ny] = true;
                    if (grid[nx][ny] == 1) {
                        return f[2] + 1;
                    }
                }
            }
        }
        return -1;
    }
}

[paopaohua]

class Solution {
    public int maxDistance(int[][] grid) {
        final int INF = 1000000;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int n = grid.length;
        int[][] d = new int[n][n];
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] status1, int[] status2) {
                return status1[0] - status2[0];
            }
        });

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = INF;
            }
        }

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

        while (!queue.isEmpty()) {
            int[] f = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int nx = f[1] + dx[i], ny = f[2] + dy[i];
                if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {
                    continue;
                }
                if (f[0] + 1 < d[nx][ny]) {
                    d[nx][ny] = f[0] + 1;
                    queue.offer(new int[]{d[nx][ny], nx, ny});
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, d[i][j]);
                }
            }
        }

        return ans == INF ? -1 : ans;
    }
}

[tiandao043]

思路

bfs 把陆地放入队列开始拓展，没有就是-1，倒着找就是最短路。

代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int dx[4]={0,1,0,-1};
        int dy[4]={1,0,-1,0};
        int n=grid.size();
        queue<pair<int,int>> q;
        vector<vector<int>> d(n,vector(n,INT_MAX));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    q.push({i,j});
                    d[i][j]=0;
                }
            }
        }

        while(!q.empty()){
            auto k=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int newx=k.first+dx[i];
                int newy=k.second+dy[i];                
                if(newx>-1&&newx<n&&newy>-1&&newy<n){                    
                    if(d[newx][newy]>d[k.first][k.second]+1){
                        d[newx][newy]=d[k.first][k.second]+1;
                        q.push({newx,newy});
                    }
                }
            }
        }
            int res=-1;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]==0&&d[i][j]<1000)res=max(res,d[i][j]);
                }
            }
            return res;        
    }
};

O(N^2)

[FlipN9]

/**
    「多源最短路」
    把所有 陆地 入队, 从各个陆地一层层向海洋扩散, 越界 or visited 过即跳过, 
                            (dist 不为 0, 陆地会是 -1, 看过的海洋会是正数)
    每一步将新的海洋入队, 更新到目前海洋的距离, 同时记录最大的 dist
    最后扩散到的海洋就是最远的海洋

    TC: O(N^2)  SC: O(N^2)
*/
class Solution {
    public int maxDistance(int[][] grid) {
        int N = grid.length;
        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int[][] dist = new int[N][N];

        int maxDist = -1;
        Queue<int[]> q = new ArrayDeque<>();

        // add land cell to queue
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    q.add(new int[] {i, j});
                    dist[i][j] = -1; // land: -1, unvisited: 0, visited ocean: positive
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            int step = Math.max(dist[x][y], 0);
            for (int[] dir : dirs) {
                int i = x + dir[0], j = y + dir[1];
                if (i < 0 || i >= N || j < 0 || j >= N) continue;
                if (dist[i][j] != 0) continue;
                q.add(new int[] {i, j});
                dist[i][j] = step + 1;
                maxDist = Math.max(maxDist, step + 1);
            }
        }

        return maxDist;
    }
}

[darwintk]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        steps = -1
        queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]
        if len(queue) == 0 or len(queue) == n ** 2: return steps
        while len(queue) > 0:
            for _ in range(len(queue)): 
                x, y = queue.pop(0)
                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:
                        queue.append((xi, yj))
                        grid[xi][yj] = -1
            steps += 1

        return steps

[Elon-Lau]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: n = len(grid) steps = -1 queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1] if len(queue) == 0 or len(queue) == n ** 2: return steps while len(queue) > 0: for _ in range(len(queue)): x, y = queue.pop(0) for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]: if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0: queue.append((xi, yj)) grid[xi][yj] = -1 steps += 1

    return steps

[Jetery]

代码 (py)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = collections.deque((i, j) for i in range(n) for j in range(n) if grid[i][j])
        if len(queue) == 0 or len(queue) == n * n:
            return -1
        else:
            while queue:
                i, j = queue.popleft()
                for p, q in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    x, y = i + p, j + q
                    if 0 <= x < n and 0 <= y < n and not grid[x][y]:
                        grid[x][y] = grid[i][j] + 1
                        queue.append((x, y))
            return grid[i][j] - 1

[heng518]

class Solution { public: int maxDistance(vector<vector>& g, int steps = 0) { queue<pair<int, int>> water, water1;

    for(int i = 0; i < g.size(); i++)
    {
        for(int j = 0; j < g[i].size(); j++)
        {
            if(g[i][j] == 1)
            {
                water.push({i-1, j});
                water.push({i+1, j});
                water.push({i, j+1});
                water.push({i, j-1});
            }
        }
    }

    while(!water.empty())
    {
        steps++;
        while(!water.empty())
        {
            int i = water.front().first;
            int j = water.front().second;
            water.pop();
            if(i >= 0 && j >= 0 && i < g[i].size() && g[i][j] == 0)
            {
                g[i][j] = steps;
                water1.push({i-1, j});
                water1.push({i+1, j});
                water1.push({i, j-1});
                water1.push({i, j+1});
            }
        }
        swap(water, water1);
    }

    return steps == 1 ? -1 : steps - 1;
}

};

[bookyue]

code

1. bfs
2. dijkstra

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        boolean[][] seen = new boolean[n][n];
        Queue<int[]> queue = new ArrayDeque<>(n * n);

        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});
                    seen[i][j] = true;
                }
            }
        }

        if (queue.size() == 0 || queue.size() == n * n) return -1;

        int dist = 0;
        while (!queue.isEmpty()) {
            dist++;
            for (int size = queue.size(); size > 0; size--) {
                var coordinate = queue.poll();
                for (int[] dir : DIRS) {
                    int x = coordinate[0] + dir[0];
                    int y = coordinate[1] + dir[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && !seen[x][y] && grid[x][y] == 0) {
                        queue.offer(new int[] {x, y});
                        seen[x][y] = true;
                    }
                }
            }
        }

        return dist - 1;
    }

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int[][] dist = new int[n][n];
        Queue<int[]> queue = new PriorityQueue<>(n * n, Comparator.comparingInt(a -> a[0]));
        boolean[][] seen = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Integer.MAX_VALUE;
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.offer(new int[] {0, i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            var p = queue.poll();
            int x = p[1];
            int y = p[2];

            if (seen[x][y]) continue;
            seen[x][y] = true;

            for (int[] dir : DIRS) {
                int nx = p[1] + dir[0];
                int ny = p[2] + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

                if (p[0] + 1 < dist[nx][ny]) {
                    dist[nx][ny] = p[0] + 1;
                    queue.offer(new int[] {dist[nx][ny], nx, ny});
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 0)
                    ans = Math.max(ans, dist[i][j]);

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

[chenming-cao]

解题思路

遍历数组，对每一个海洋位置进行BFS，算出到达陆地的最近距离，同时记录当前距离的最大值。遍历结束返回最大值即可。可以转换思路从陆地开始遍历。

代码

class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int max = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    max = Math.max(max, bfs(grid, i, j));
                }
            }
        }
        return max;
    }

    private int bfs(int[][] grid, int row, int col) {
        int n = grid.length;
        Deque<int[]> queue = new LinkedList<>(); // information stored in the queue, {x, y, distance}
        boolean[][] visited = new boolean[n][n];
        queue.offer(new int[]{row, col, 0});
        visited[row][col] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            // iterate 4 directions
            for (int i = 0; i < 4; i++) {
                int x = cur[0] + dx[i];
                int y = cur[1] + dy[i];
                // check whether index is valid
                if (!(x >= 0 && x < n && y >= 0 && y < n)) continue;
                // check whether new position is visited, if not, put in the queue
                if (!visited[x][y]) {
                    queue.offer(new int[]{x, y, cur[2] + 1});
                    visited[x][y] = true;
                    // return distance if reaching a land
                    if (grid[x][y] == 1) return cur[2] + 1;
                }
            }
        }
        return -1;      
    }
}

复杂度分析

• 时间复杂度：O(n^4)，总共进行n^2次BFS，最坏情况是全部为海洋，每次BFS的时间复杂度为O(n^2)，总共为O(n^4)。
• 空间复杂度：O(n^2)

[Elsa-zhang]

''' 1162. 地图分析
    陆地1 海洋0
'''
class Solution:
    def maxDistance(self, grid: list[list[int]]):

        n = len(grid)
        q = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]

        if len(q) == 0 or len(q) == n ** 2: 
            return -1

        steps = -1
        while(len(q)>0):
            for _ in range(len(q)):
                x, y = q.pop(0)
                for xx, yy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if xx < 0 or xx >= n or yy < 0 or yy >= n:
                        continue
                    if grid[xx][yy] != 0:
                        continue
                    q.append((xx, yy))
                    grid[xx][yy] = -1

            steps += 1
        return steps

grid = [[1,0,1],[0,0,0],[1,0,1]]
solution = Solution()
ans = solution.maxDistance(grid)
print(ans)