【Day 51 】2023-04-05 - 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

[Zoeyzyzyzy]

class Solution {
    // BFS,利用陆地扩张来找到最后的答案
    // Time Complexity: O(n^2), Space Complexity: O(n^2);
    public int maxDistance(int[][] grid) {
        int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int m = grid.length;
        int n = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        //先把所有陆地入队
        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[] land = null;
        while (!queue.isEmpty()) {
            land = queue.poll();
            //将四周海洋入队
            for (int[] direction : directions) {
                int newX = land[0] + direction[0];
                int newY = land[1] + direction[1];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0)
                    continue;
                grid[newX][newY] = grid[land[0]][land[1]] + 1;
                hasOcean = true;
                queue.offer(new int[] { newX, newY });
            }
        }
        //没有陆地or没有海洋的情况
        if (!hasOcean || land == null)
            return -1;

        //返回最后遍历到的海洋到陆地的距离，由于初始陆地坐标为1，故需要增加1
        return grid[land[0]][land[1]] - 1;
    }
}

[JiangyanLiNEU]

• BFS

  class Solution:
  def maxDistance(self, grid: List[List[int]]) -> int:
      self.directions = [[1,0],[0,1],[-1,0],[0,-1]]
      self.distance = [[0 for _ in grid[0]] for _ in grid]
      self.res = -1
      level = []
      seen = set([])
  
      def inBound(r, c):
          return r>=0 and c>=0 and r<len(grid) and c<len(grid[0])
  
      for row in range(len(grid)):
          for col in range(len(grid[0])):
              if grid[row][col] == 1:
                  level.append([row, col])
                  seen.add((row, col))
  
      while level:
          nextLevel = []
          for row, col in level:
              for dx, dy in self.directions:
                  newR, newC = dx+row, dy+col
                  if inBound(newR, newC) and grid[newR][newC] == 0 and (newR, newC) not in seen:
                      seen.add((newR, newC))
                      self.distance[newR][newC] = self.distance[row][col]+1
                      self.res = max(self.res, self.distance[newR][newC])
                      nextLevel.append([newR, newC])
          level = nextLevel
      return self.res

[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

[lp1506947671]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        steps = -1
        queue = collections.deque([(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.popleft(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

复杂度分析

• 时间复杂度：由于 grid 中的每个点最多被处理一次，因此时间复杂度为 O(N^2)
• 空间复杂度：由于我们使用了队列，而队列的长度最多是 n^2，这种情况其实就是全为 1 的 grid，因此空间复杂度为 O(N^2)

[airwalkers]

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;
    }
}

[FireHaoSky]

思路：多远bfs

代码：python

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

        # 将所有陆地的位置入队
        q = deque()
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    q.append((i, j))

        if len(q) == 0 or len(q) == n * m:
            # 特判：如果地图上没有陆地或者所有位置都是陆地，则返回 -1
            return -1

        ans = -1
        while q:
            # 多源 BFS，从多个起点开始搜索
            size = len(q)
            for i in range(size):
                x, y = q.popleft()

                # 对于每个起点，向四个方向扩展
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx, ny = x + dx, y + dy

                    # 判断扩展出的新位置是否越界
                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue

                    # 判断扩展出的新位置是否为陆地或者已经访问过
                    if grid[nx][ny] == 1 or grid[nx][ny] == 2:
                        continue

                    # 标记当前位置已经访问过，并将其入队
                    grid[nx][ny] = 2
                    q.append((nx, ny))

            # 每搜索一层，位置加 1
            ans += 1

        # 返回位置的最大值即为所求
        return ans

复杂度分析：

"""
时间复杂度：o(NM)
空间复杂度：O（NM）
"""

[JasonQiu]

• BFS

  class Solution:
  def maxDistance(self, grid: List[List[int]]) -> int:
      lands = []
      n = len(grid)
      m = len(grid[0])
      dx = [0, 0, 1, -1]
      dy = [1, -1, 0, 0]
      for i in range(n):
          for j in range(m):
              if grid[i][j] == 1:
                  lands.append((i, j))
      if len(lands) == 0 or len(lands) == n * m:
          return -1
      while lands:
          (x, y) = lands.pop(0)
          for i in range(4):
              next_x = x + dx[i]
              next_y = y + dy[i]
              if 0 <= next_x < n and 0 <= next_y < m and grid[next_x][next_y] == 0:
                  grid[next_x][next_y] = grid[x][y] + 1
                  lands.append((next_x, next_y))
      return grid[x][y] - 1

  Time: O(n^2) Space: O(n^2)

[harperz24]

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

        max_dist = 0
        n = len(grid)
        land_q = collections.deque()
        visited = set()

        def isNewSource(i, j):
            return 0 <= i < n and 0 <= j < n and (i, j) not in visited and grid[i][j] == 0

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    land_q.append((r, c, 0))
                    visited.add((r, c))

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

        while land_q:
            len_q = len(land_q)
            for _ in range(len_q):
                r, c, dist = land_q.popleft()
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    new_r = r + dr
                    new_c = c + dc

                    if isNewSource(new_r, new_c):
                        land_q.append((new_r, new_c, dist + 1))
                        visited.add((new_r, new_c))
                        max_dist = max(max_dist, dist + 1)
        return max_dist

        # multisource bfs
        # time: O(n**2)
        # space: O(**2)

[wangzh0114]

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

    int n;
    int d[MAX_N][MAX_N];

    struct Coordinate {
        int x, y;
    };

    queue <Coordinate> q;

    int maxDistance(vector<vector<int>>& grid) {
        this->n = grid.size();
        auto &a = grid;

        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 (a[i][j]) {
                    d[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        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 <= n - 1)) continue;
                if (d[nx][ny] > d[f.x][f.y] + 1) {
                    d[nx][ny] = d[f.x][f.y] + 1;
                    q.push({nx, ny});
                }
            }
        }

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

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

[bookyue]

TC: O(n^2)
SC: O(n^2)

    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.isEmpty() || queue.size() == n * n) return -1;

        int dist = 0;
        while (!queue.isEmpty()) {
            dist++;
            for (int size = queue.size(); size > 0; size--) {
                int[] 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;
    }

[sye9286]

代码

var maxDistance = function(grid) {
    var result=-1; 
    var land=[];
    var row = grid.length;
    var col = grid[0].length;
    for(var i=0;i<row;i++){ 
        for(var j=0;j<col;j++){
            if(grid[i][j]==1){
                land.push([i,j]);
            }
        }
    }

    if(land.length==0 || land.length == row*col){return -1;}

    while(land.length>0){
        var size=land.length;
        while(size>0){
            size--;
            var cur=land.shift();

            var directions=[[-1,0],[0,1],[1,0],[0,-1]];
            for(var i=0;i<4;i++){
                var r = cur[0] + directions[i][0];
                var c = cur[1] + directions[i][1];

                if(r<0 || r>col-1 || c<0 || c>row-1 || grid[r][c]==1){
                    continue;
                }

                if(grid[r][c]==0){
                    grid[r][c]=1;
                    land.push([r,c]);
                }
            }
        }
        result++;
    }
    return result;
};

复杂度分析

• 时间复杂度：O(N^2)
• 空间复杂度：O(N^2)

[Size-of]

/**

• @param {number[][]} grid

• @return {number} */ var maxDistance = function(grid) { const n = grid[0].length const DIR = [[1,0], [0,1], [-1,0], [0,-1]]

  const legal = (x,y) =>{ if(x < 0 || y < 0 || x >= n || y >= n) return false return true }

  const dis = Array.from({length:n}).map(()=> Array.from({length:n}).fill(Number.MAX_SAFE_INTEGER)) const queue = []

  for(let i = 0; i < n;i++){ for(let j = 0; j < n; j++){ if(grid[i][j] == 1){ dis[i][j] = 0 queue.push([i,j]) } } }

  while(queue.length){ const [x,y] = queue.shift()

  for(const d of DIR){
      let nx = d[0] + x
      let ny = d[1] + y
  
      if(legal(nx,ny) && dis[x][y] + 1 < dis[nx][ny]){
          dis[nx][ny] = dis[x][y] + 1
          queue.push([nx,ny])
      }
  }

  }

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

  return ans == Number.MAX_SAFE_INTEGER ? -1 : ans };

[RestlessBreeze]

code

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;
    }
};

[Diana21170648]

思路

BFS广度优先搜索算法

代码

# bfs广度优先搜索算法
# 定义一个函数，用于找到海洋单元格到最近陆地单元格的最大曼哈顿距离
from turtle import distance
grid = [[1, 0, 1],
        [0, 0, 0],
        [1, 0, 1]]

def max_distance(grid):
    # 定义四个方向的偏移量
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    # 定义一个队列，用于存储陆地单元格
    queue = []
    # 将所有陆地单元格加入队列，并将其标记为已访问
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                queue.append((i, j))
                grid[i][j] = -1
    # 如果没有陆地单元格或者没有海洋单元格，返回-1
    if len(queue) == 0 or len(queue) == len(grid) * len(grid[0]):
        return -1
    # 定义一个变量，用于记录曼哈顿距离
    distance = 0
    # 不断从队列中取出陆地单元格，并将其周围的海洋单元格加入队列
    while queue:
        size = len(queue)
        for i in range(size):
            x, y = queue.pop(0)
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # 如果新的位置越界或者已经访问过，跳过
                if nx < 0 or nx >= len(grid) or ny < 0 or ny >= len(grid[0]) or grid[nx][ny] != 0:
                    continue
                # 将新的位置标记为已访问，并将其加入队列
                grid[nx][ny] = grid[x][y] - 1
                queue.append((nx, ny))
        # 每遍历一圈，曼哈顿距离加1
        distance += 1
    # 返回曼哈顿距离的最大值
    return distance
# 输出地图最大距离
print(distance)

**复杂度分析**
- 时间复杂度：O(N^2)，每个点最多被处理一次
- 空间复杂度：O(N^2)，使用队列，队列最大长度为N^2

[aoxiangw]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c]:
                    q.append([r,c])
        res = -1
        direct = [[0,1],[1,0],[0,-1],[-1,0]]
        while q:
            r, c = q.popleft()

            res = grid[r][c]
            for dr,dc in direct:
                newR, newC = r + dr, c + dc
                if (min(newR, newC) >= 0 and
                    max(newR, newC) < N and
                    grid[newR][newC] == 0):
                    q.append([newR, newC])
                    grid[newR][newC] = grid[r][c] + 1
        return res - 1 if res > 1 else -1

time, space: O(n^2), O(n^2)

[Lydia61]

1162. 地图分析

思路

深度优先遍历

代码

    def maxDistance(self, grid: List[List[int]]) -> int:
        ans = -1
        n = len(grid)
        queue = collections.deque()
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i,j))

        if  len(queue) == n**2:
            return -1

        while queue:
            ans += 1
            queue_copy = queue.copy()
            queue = collections.deque()
            for x,y in queue_copy:
                if x + 1 < n and not grid[x + 1][y]:
                    grid[x+1][y] = grid[x][y] + 1
                    queue.append((x+1,y))
                if y + 1 < n and not grid[x ][y + 1]:
                    grid[x][y + 1] = grid[x][y] + 1
                    queue.append((x,y+1))
                if x - 1 >= 0 and not grid[x - 1][y]:
                    grid[x-1][y] = grid[x][y] + 1
                    queue.append((x-1,y))
                if y - 1 >=0 and not grid[x ][y - 1]:
                    grid[x][y - 1] = grid[x][y] + 1
                    queue.append((x,y - 1))
        return  ans

复杂度分析

• 时间复杂度：O(N^2)
• 空间复杂度：O(N^2)

[NorthSeacoder]

var maxDistance = function(grid) {
    var result = -1; //距离
    var land = []; //存放陆地的队列
    var n = grid.length; //行数
    for (var i = 0; i < n; i++) {
        // 所有陆地入队
        for (var j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                land.push([i, j]);
            }
        }
    }
    //全是海洋或者陆地
    if (land.length == 0 || land.length == n * n) {
        return -1;
    }
    //对每一块陆地进行BFS，对每一块遍历过的海洋标记成陆地
    while (land.length > 0) {
        var size = land.length; //记录当前层陆地的个数
        while (size > 0) {
            size--;
            var cur = land.shift(); //第一个入队的陆地
            //四个方向
            var directions = [
                [-1, 0],
                [0, 1],
                [1, 0],
                [0, -1]
            ];
            for (var i = 0; i < 4; i++) {
                var r = cur[0] + directions[i][0];
                var c = cur[1] + directions[i][1];
                //越界，跳过此方向
                if (r < 0 || r > n - 1 || c < 0 || c > n - 1 || grid[r][c] == 1) {
                    continue;
                }
                //如果是海洋，标记为陆地，加入到队列中，距离＋1
                if (grid[r][c] == 0) {
                    grid[r][c] = 1;
                    land.push([r, c]);
                }
            }
        }
        result++;
    }
    return result;
};

• TC:O(n^2)
• SC:O(n^2)

[kangliqi1]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: n = len(grid) steps = -1 queue = collections.deque([(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.popleft(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

[yingchehu]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        q = collections.deque([(x, y) for y in range(n) for x in range(n) if grid[x][y] == 1])
        if len(q) == 0 or len(q) == n ** 2: return -1

        step = -1
        while q:
            step += 1
            for _ in range(len(q)):
                point = q.popleft()
                for (x, y) in [(point[0]+1, point[1]), (point[0]-1, point[1]), (point[0], point[1]+1), (point[0], point[1]-1)]:
                    if x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 0:
                        q.append((x, y))
                        grid[x][y] = -1

        return step

[Fuku-L]

代码

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[] s1, int[] s2){
                return s1[0] - s2[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 = ans > d[i][j] ? ans : d[i][j];
                }
            }
        }
        return ans == INF ? -1 : ans;

    }
}

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为二维数组长度。
• 空间复杂度：O(N^2)

[Jetery]

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};

        int n = grid.size(), m = grid[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> dis(n, vector(m, INT_MAX));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1) {
                    q.push(make_pair(i, j));
                    dis[i][j] = 0;
                }

        while (!q.empty()) {
            auto u = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int x = u.first + dx[i], y = u.second + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;

                if (dis[x][y] > dis[u.first][u.second] + 1) {
                    dis[x][y] = dis[u.first][u.second] + 1;
                    q.push(make_pair(x, y));
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 0 && dis[i][j] < INT_MAX)
                    ans = max(ans, dis[i][j]);

        return ans;
    }
};

[Meisgithub]

class Solution {
public:
    int neighbors[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int ans = -1;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 0)
                {
                    // cout << i << ' ' << j << ' ' << bfs(grid, i, j) << endl;
                    ans = max(ans, bfs(grid, i, j));
                }
            }
        }
        return ans;
    }

    int bfs(const vector<vector<int>>& grid, int i, int j)
    {
        int n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0));
        int step = -1;
        queue<pair<int, int>> q;
        q.emplace(i, j);
        visited[i][j] = 1;
        while (!q.empty())
        {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; ++i)
            {
                pair<int, int> pos = q.front();
                q.pop();

                if (grid[pos.first][pos.second] == 1)
                {
                    return step;
                }
                for (auto &neighbor : neighbors)
                {
                    int newI = pos.first + neighbor[0];
                    int newJ = pos.second + neighbor[1];
                    if (newI >= 0 && newI < n && newJ >= 0 && newJ < n && !visited[newI][newJ])
                    {
                        q.emplace(newI, newJ);
                        visited[newI][newJ] = 1;
                    }
                }
            }

        }
        return -1;
    }
};

[chocolate-emperor]

class Solution {
public:

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

   //求每个water最近的land的距离，找距离集合中的最大值
   //因为每一个步长是相等的，所以可以用bfs搜索，距离为1，2，3，4，最先搜到的一定是最近的
   //最近距离 = bfs的层数 -》最大的最近距离，bfs的最大层数
    int maxDistance(vector<vector<int>>& grid) {
        int len = grid.size();    
        int mem[104][104]={0};

        queue<pair<int,int>>q;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(grid[i][j]==1)   {
                    q.push(make_pair(i,j));
                    mem[i][j] = 1;
                }
            }
        }

        if(q.empty()||q.size()==len*len)    return -1;

        int dis = -1;
        while(!q.empty()){
            int l = q.size();
            for(int i=0;i<l;i++){
                pair<int,int> tmp = q.front();
                q.pop();
                int x = tmp.first, y = tmp.second;
                for(int j=0;j<4;j++){
                    int ne_x = x+dx[j], ne_y = y+dy[j];
                    if(ne_x>=0 && ne_x<len && ne_y>=0 && ne_y<len && 0==mem[ne_x][ne_y]){
                        mem[ne_x][ne_y]=1;
                        q.push(make_pair(ne_x,ne_y));
                    }
                }

            }
            dis+=1;
        }
        return dis;
    }
};

[X1AOX1A]

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        steps = -1
        queue = collections.deque([(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.popleft(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

[joemonkeylee]

var maxDistance = function(grid) { let m = grid.length; let n = grid[0].length;

let array = [];
for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (grid[i][j] === 1) {
            array.push([i, j]);
        }
    }
}
if (array.length === 0 || array.length === m * n) return -1;

const col = [-1, 1, 0, 0];
const row = [0, 0, -1, 1];

let temp = [];
while (array.length) {
    temp = array.pop();
    const x = temp[0];
    const y = temp[1];

    for (let i = 0; i < 4; i++) {
        const xx = x + col[i];
        const yy = y + row[i];
        if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] !== 0) {
            continue;
        } else {
            grid[xx][yy] = grid[x][y] + 1;
            array.unshift([xx, yy]);
        }
    }
}
return grid[temp[0]][temp[1]] - 1;

};

[snmyj]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: r, c = len(grid), len(grid[0]) data = list() for i in range(r): for j in range(c): if grid[i][j] == 1: data.append((i, j, 0))

    d = [(0,1), (0,-1), (1,0), (-1,0)]
    res = 0
    while data:
        i, j, res = data.pop(0)
        for xd, yd in d:
            x, y = i + xd, j + yd
            if 0 <= x < r and 0 <= y < c and grid[x][y] == 0:
                grid[x][y] = 1
                data.append((x, y, res+1))

    return res if res != 0 else -1

[GuitarYs]

class Solution: def maxDistance(self, grid: List[List[int]]) -> int: r, c = len(grid), len(grid[0]) data = list() for i in range(r): for j in range(c): if grid[i][j] == 1: data.append((i, j, 0))

d = [(0,1), (0,-1), (1,0), (-1,0)]
res = 0
while data:
    i, j, res = data.pop(0)
    for xd, yd in d:
        x, y = i + xd, j + yd
        if 0 <= x < r and 0 <= y < c and grid[x][y] == 0:
            grid[x][y] = 1
            data.append((x, y, res+1))

return res if res != 0 else -1

[kofzhang]

思路

广度优先搜索

复杂度

时间复杂度：O(n^2) n为行或列的数量 空间复杂度：O(n^2)

代码

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        q = deque()
        n = len(grid)
        d = [(-1,0),(1,0),(0,-1),(0,1)]
        for row in range(n):
            for col in range(n):
                if grid[row][col]==1:
                    for x,y in d:
                        if 0<=row+x<n and 0<=col+y<n and grid[row+x][col+y]==0:
                            q.append((row+x,col+y,1))
        res = -1
        while q:
            row,col,dist = q.popleft()
            if grid[row][col] != 0:
                continue
            grid[row][col]=dist
            for x,y in d:
                if 0<=row+x<n and 0<=col+y<n and grid[row+x][col+y]==0:
                    q.append((row+x,col+y,dist+1))                
            res = dist        
        return res

[texamc2]

type Point struct {
    X int
    Y int
}

func maxDistance(grid [][]int) int {
    var queue []*Point
    for i:=0; i < len(grid); i++ {
        for j:=0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                queue = append(queue, &Point{i, j})
            }
        }
    }
    if len(queue) == 0 || len(queue) == len(grid)*len(grid[0]) {
        return -1
    }

    ans := 0
    d := [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
    for len(queue) > 0 {
        ans++
        tmpQueu := queue
        queue = nil
        for len(tmpQueu) > 0 {
            p := tmpQueu[0]
            tmpQueu = tmpQueu[1:]
            for i:=0; i < 4; i++ {
                x := p.X + d[i][0]
                y := p.Y + d[i][1]
                if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) || grid[x][y] != 0 {
                    continue
                }
                queue = append(queue, &Point{x, y})
                grid[x][y] = 2 
            }
        }
    }

    return ans-1
}

[chanceyliu]

代码

function maxDistance(grid: number[][]): number {
  if (grid.length < 2) return -1;
  let n = grid.length;
  // 创建 dp 状态矩阵
  let dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(n);
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      dp[i][j] = grid[i][j] ? 0 : Infinity;
    }
  }
  // 从左上向右下遍历
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) continue;
      if (i - 1 >= 0) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
      if (j - 1 >= 0) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
    }
  }
  // 从右下向左上遍历
  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (grid[i][j]) continue;
      if (i + 1 < n) dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
      if (j + 1 < n) dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
    }
  }
  let ans = -1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (!grid[i][j]) ans = Math.max(ans, dp[i][j]);
    }
  }
  if (ans === Infinity) {
    return -1;
  } else {
    return ans;
  }
}