search

leetcode-pp / 91alg-7-daily-check

6 stars 0 forks source link

【Day 51 】2022-05-21 - 1162. 地图分析 #56

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

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：

image


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

image


输入：[[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
zqwwei commented 2 years ago

Code

class Solution {
    public int maxDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    visited[i][j] = true;
                    q.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int result = -1;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                result = Math.max(result, grid[cur[0]][cur[1]] - 1);
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0], y = cur[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
                        visited[x][y] = true;
                        grid[x][y] = grid[cur[0]][cur[1]] + 1;
                        q.offer(new int[]{x, y});
                    }
                }
            }
        }
        return result == 0 ? -1 : result;
    }
}
Jongeehsu commented 2 years ago 
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});
            }
        }

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

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

    }
}
MichaelXi3 commented 2 years ago

Idea

虽然 BFS 一般是用于找到 a 到 b 的最短距离使用，但本题也可以使用 BFS 来从陆地节点开始，逐步探索 water regions，同时记录走过的 steps，并最终通过走完全部的 grids 查看最远的 water block 走出来多少步才到就是我们想要的最终答案。

Code

class Solution {
    public int maxDistance(int[][] grid) {
        // Create a chart to track the status of "isVisited"
        // Create a Queue to store the coordinates of points for BFS
        // We start from the land areas and expand to water to see how far we can go
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    isVisited[i][j] = true;
                    q.offer(new int[] {i, j});
                }
            }
        }

        // The expansion from land to water region begins
        // The expansion includes four directions
        int res = -1;
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // left, right, down, up
        while (!q.isEmpty()){
            int[] cur = q.poll();
            // Distance since start to currPoint, initial distance from land is 0, if all water or land then res=-1
            res = Math.max(res, grid[cur[0]][cur[1]] - 1); 
            // Explore from currPoint to four directions
            for (int[] dir: directions) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                // if within boundary and has not been visited
                if (x>=0 && x<m && y>=0 && y<n && !isVisited[x][y]){
                                      // record that we move one more step in our expansion
                    grid[x][y] = grid[cur[0]][cur[1]] + 1; 
                    isVisited[x][y] = true; // mark as visited
                    q.offer(new int[] {x, y});
                }
            }
        }
                 // All lands situation will lead to res=0, but we should return -1
        if (res == 0) { return -1; } else { return res; }
    }
}

Complexity

Let n be the total number of blocks in grid

  • Time: O(n)
  • Space: O(n)
JiangWenqi commented 2 years ago

C++

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int dirs[5] = {0, 1, 0, -1, 0};
        int res = -1;
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    q.push(make_pair(i, j));
                    // make it visited
                    grid[i][j] = -1;
                }
            }
        }
        // if all cell are sea or lands, return -1
        if (q.empty() || q.size() == m * n) return res;

        while (!q.empty()) {
            int num = q.size();
            for (int k = 0; k < num; k++) {
                int x = q.front().first, y = q.front().second;
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int nx = x + dirs[i], ny = y + dirs[i + 1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        grid[nx][ny] = -1;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
            res++;
        }
        return res;
    }
};

O(n) O(n)

zhulin1110 commented 2 years ago

题目地址(1162. 地图分析)

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

题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

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

 

示例 1：

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

示例 2：

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

 

提示：

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

前置知识

代码

JavaScript Code:


/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
   let n = grid.length;
    let queue = [];

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            // 将所有陆地加入队列，而不是海洋，陆地不断扩展到海洋
            if (grid[i][j] == 1) {
                queue.push([i, j]);
            }
        }
    }

    let ans = -1;
    // 都是海洋 或 都是陆地
    if (queue.length === 0 || queue.length === n * n) {
        return ans;
    }

    // 方向数组
    let locations = [[0, -1], [0, 1], [-1, 0], [1, 0]];

    while (queue.length != 0) {
        let len = queue.length;

        // 对每个陆地4个方向搜索
        for (let k = 0; k < len; k++) {
            let [x, y] = queue.shift();
            // 向该点的4个方向进行搜索
            for (let location of locations) {
                let nextI = x + location[0];
                let nextJ = y + location[1];

                // 合法 且 是海洋
                if (nextI >= 0 && nextI < n && nextJ >=0 && nextJ < n && grid[nextI][nextJ] == 0) { 
                    grid[nextI][nextJ] = 1; // 变为陆地
                    queue.push([nextI, nextJ]);
                }
            }
        }
        ans++;
    }
    return ans;
};

复杂度分析

currybeefer commented 2 years ago

思路就是DFS，直接做就好。自己写的太慢了，最后还是参考了题解的

 const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};    
    int maxDistance(vector<vector<int>>& grid) 
    {
        int N = grid.size();
        queue<pair<int, int>> q; // queue存储坐标值, 即 pair of {x, y}
        vector<vector<int>> d(N, vector(N, 1000)); // 二维数组d[][]: 记录每个格子grid[i][j]的距离值
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                if (grid[i][j] == 1)
                {
                    q.push(make_pair(i, j));
                    d[i][j] = 0;
                }            
        }
        while (!q.empty())
        {
            auto kvp = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int newX = kvp.first + dx[i], newY = kvp.second + dy[i];
                if (newX < 0 || newX >= N || newY < 0 || newY >= N) // 越界了, 跳过
                    continue;

                if (d[newX][newY] > d[kvp.first][kvp.second] + 1) /* 如果从水域(值为0的格子)走到陆地(值为1的格子)或从陆地走到水域, 且新到达的位置之前没被访问过, 此时需要将其坐标加入队列, 并更新距离值d */
                {
                    d[newX][newY] = d[kvp.first][kvp.second] + 1; /* 当前格子的上下左右4个方向之一走一步恰好使得曼哈顿距离增加1 */
                    q.push(make_pair(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] <= 200) /* 挑出访问过的水域位置(值为0的格子), 并维护这些格子中距离值d的最大值 */
                    res = max(res, d[i][j]);
            }
        }
        return res;
    }
ShawYuan97 commented 2 years ago

思路

使用BFS去探索陆地与海洋的距离 首先将陆地全部加入队列，然后遍历所有陆地间隔为1的海洋，并将遍历后的海洋标记为-1； 相当于将海洋变成了大陆，继续探索新的海洋，每层队列step+1； 直到没有新的海洋探索了，那么就可以得出距离最近大陆的距离最大值

关键点

代码

Python3 Code:


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

复杂度分析

令 n 为数组长度,K为大陆个数。

houmk1212 commented 2 years ago

思路

自己最开始是BFS海洋位置的，导致有很多重复的搜索过程，超时。看了题解，了解了优化的方法；

代码

class Solution1162 {
    boolean[][] visit;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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

    public int BFS(int[][] grid, int x, int y) {
        int n = grid.length;
        Deque<int[]> queue = new ArrayDeque<>();
        int originalX = x;
        int originalY = y;
        visit[x][y] = true;
        queue.add(new int[]{x, y});
//        int level = 0;
        while (!queue.isEmpty()) {
//            level++;
            int[] tmp = queue.pop();
            x = tmp[0];
            y = tmp[1];
            visit[x][y] = true;
            if (grid[x][y] == 1) {
                return Math.abs(x - originalX) + Math.abs(y - originalY);
            }
            for (int i = 0; i < 4; i++) {
                int nextX = x + directions[i][0];
                int nextY = y + directions[i][1];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !visit[nextX][nextY]) {
                    queue.add(new int[]{nextX, nextY});
                }
            }
        }
        return -1;
    }
}
zjsuper commented 2 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        #transform to max (every 0 to 1 min distance)
        n = len(grid)
        ans = []
        sums  = 0
        for i in grid:
            for j in i:
                sums += j
        if sums == 0 or sums == n*n:
            return -1

        for i in range(n):
            for j in range(n):
                #print(grid)
                if grid[i][j] == 0:
                    #print(i,j)
                    #p#rint(self.dfs((i,j),grid))
                    ans.append(self.bfs((i,j),grid)) 
        return max(ans)

    def bfs(self,start_pos,grids):
        visited = set((start_pos))
        n = len(grids)
        ans = 1000
        queue = deque()
        queue.append([start_pos,0])
        directions = [(1,0),(-1,0),(0,-1),(0,1)]
        while queue:
            temp = queue.popleft()
            r,c = temp[0]
            distance = temp[1]
            #ans = min(distance,ans)
            for i,j in directions:
                if -1<r+i and r+i<n and -1<c+j and c+j<n:
                    if (r+i,c+j) not in visited:
                        visited.add((r+i,c+j))
                        if grids[r+i][c+j] == 1:
                            ans = min(distance+1,ans)
                            return ans
                        elif grids[r+i][c+j] == 0:
                            queue.append([(r+i,c+j),distance+1])
        return -1
zhiyuanpeng commented 2 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        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
        step = -1
        move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while len(que):
            for _ in range(len(que)):
                nx, ny = que.popleft()
                for di, dj in move:
                    x = nx + di
                    y = ny + dj
                    if 0 <= x < N and 0 <= y < N and grid[x][y] == 0:
                        que.append((x, y))
                        grid[x][y] = -1
            step += 1
        return step
shawnhu23 commented 2 years ago

Idea

BFS

Code (from discussion)

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

        int n = grid.length;
        int m = grid[0].length;
        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    queue.add(i * m + j);
                }
            }
        }

        if(queue.size() == 0 || queue.size() == n * m) {     //Found no 1's in the grid  //Empty queue
            return -1;                                       //Found no 0's in the grid  //Full queue
        }

        int level = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0){
                int idx = queue.poll();
                int r = idx / m;
                int c = idx % m;
                for(int d = 0; d < dir.length; d++) {
                    int x = r + dir[d][0];
                    int y = c + dir[d][1];
                    if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0) {
                        queue.add(x * m + y);
                        grid[x][y] = 1;
                    }
                }
            }
            level++;
        }
        return level - 1;
    }
}

Complexity

Time: O(MN)

xil324 commented 2 years ago 
class Solution(object):
    def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        ans = 0;
        queue = collections.deque(); 
        visited = set(); 
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    queue.append((i,j)); 
                    visited.add((i,j)); 
        if len(queue) == 0 or len(queue) == len(grid) ** 2:
            return -1; 
        while queue:
            ans += 1; 
            for _ in range(len(queue)):
                x,y = queue.popleft();
                for direction in [(0,1), (0,-1), (1,0), (-1,0)]:
                    new_x = direction[0] + x;
                    new_y = direction[1] + y;
                    if 0<=new_x<len(grid) and 0<=new_y<len(grid[0]) and grid[new_x][new_y] == 0:
                        if (new_x,new_y) in visited:
                            continue;
                        queue.append((new_x, new_y));
                        visited.add((new_x, new_y)); 
        return ans-1;

time compleixty: O(n^2)

xingchen77 commented 2 years ago

思路

BFS来求解

代码

    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()
                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

复杂度

时间 O(n^^2) \ 空间 O(n^^2)

xiayuhui231 commented 2 years ago

题目

地图分析

代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
using P = pair<int, int>;
        int n = grid.size();
        queue<P> q;
        vector<vector<int>> dis(grid);
        // 把所有陆地加进队列，作为源节点
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j])
                {
                    dis[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        // 判断是否都是海洋或者陆地
        if (q.size() == n * n || q.empty()) return -1;
        int res = 0;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        while (!q.empty())
        {
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                int x = q.front().first, y = q.front().second;
                q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int tx = x + dx[i], ty = y + dy[i];
                    if (tx >= 0 && tx < n && ty >= 0 && ty < n && !grid[tx][ty])
                    {
                        grid[tx][ty] = 1;
                        q.push({tx, ty});
                        // 记录从源出发的距离
                        dis[tx][ty] = dis[x][y] + 1;
                        // 记录最远距离
                        res = max(res, dis[tx][ty]);
                    }
                }
            }
        }
        return res;
    }
};

复杂度

时间复杂度:O(n) 空间复杂度:O(n)

yinhaoti commented 2 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        """
        bfs - queue
        TC: O(n^2)
        SC: O(n^2)
        """
        n = len(grid)
        steps = -1
        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) == 0 or len(queue) == n * n:
            return -1

        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                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
Geek-LX commented 2 years ago

5.21

思路:BFS

代码：

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

复杂度分析:

O(N2)

antmUp commented 2 years ago

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
KWDFW commented 2 years ago

Day51

1162、地图分析

javascript #bfs

思路

1、遍历矩阵，记录海洋数目，将陆地坐标入队

2、广度优先搜索，每次都把陆地向四周扩散，把海洋变成陆地

3、当海洋为空时，即为最大深度

代码

var maxDistance = function(grid) {
  let queue=[]//记录陆地
  let areaCount=0//记录海洋
  for(let i=0;i<grid.length;i++){//遍历矩阵
    for(let j=0;j<grid[0].length;j++){
      if(grid[i][j]){
        queue.push([i,j])//陆地放入队列中
      }
      else{
        areaCount++//记录海洋的个数
      }
    }
  }
  if(areaCount===0||queue.length===0){
    return -1
  }//只有陆地或海洋，返回-1
  const directions=[//方向数组
    [0,1],[0,-1],[1,0],[-1,0]
  ]
  let depth=0//记录bfs的深度
  while(queue.length){//遍历完陆地
    const size=queue.length
    //记录当前的陆地个数
    depth++
    //每次遍历下一层时，增加深度
    for(let k=0;k<size;k++){//遍历当前层的陆地
      let [i,j]=queue.shift()
      //取队首陆地的坐标
      for(let n of directions){
        let newI=n[0]+i
        let newJ=n[1]+j
        //找队首陆地的四个方向
      if(newI<0||
        newJ<0||
        newI>=grid.length||
        newJ>=grid[0].length||
        grid[newI][newJ]===1)
      {
        continue
      }//如果是非海洋，则跳过这个方向
      grid[newI][newJ]=1
      queue.push([newI,newJ])
      areaCount--
      //把海洋变成陆地
      if(areaCount==0) return depth
      //当海洋消失时，求得最大距离
      }
    }
  }
  return -1
};

复杂度分析

时间复杂度：O(n2)

空间复杂度：O(n2)

Ellie-Wu05 commented 2 years ago

class Solution: def maxDistance(self, grid):

    rows = len(grid)
    if rows == 0:
        return -1

    cols = len(grid[0])
    lands = collections.deque()

    maxDistance = 0

    # 找到所有陆地 并且 陆地和陆地自己的距离为0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                lands.append([(i,j), 0])

    while lands:
        for _ in range(len(lands)):

            temp = lands.popleft()
            x,y = temp[0] 
            d = temp[1]

            maxDistance = max(maxDistance, d)

            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                xx, yy = x + dx, y + dy

                # edge cases
                if xx < 0 or xx == rows or yy < 0 or yy == cols:
                    continue

                if grid[xx][yy] == 0:

                    grid[xx][yy] = d + 1
                    lands.append([(xx, yy), d + 1])

    return maxDistance or -1
Magua-hub commented 2 years ago 

class Solution {
public:

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        deque<pair<int, int>> deq;
        for(int i = 0; i < n; i ++) 
            for(int j = 0; j < m; j ++) {
                if(grid[i][j]) {
                    deq.push_back({i, j});
                }
            }

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

        int dis = -1;
        while(deq.size() != 0) {
            dis ++;
            int size = deq.size();
            while(size --) {
                auto cur = deq.front();
                deq.pop_front();
                for(int i = 0; i < 4; i ++) {
                    int x = cur.first + dx[i], y = cur.second + dy[i];
                    if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 0) continue;
                    grid[x][y] = 2;
                    deq.push_back({x, y});
                }
            }
        }
        return dis; 
    }
};
testeducative commented 2 years ago 

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 Status {
        int v, x, y;
        bool operator < (const Status &rhs) const {
            return v > rhs.v;
        }
    };

    priority_queue <Status> 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({0, i, j});
                }
            }
        }

        while (!q.empty()) {
            auto f = q.top(); 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 (f.v + 1 < d[nx][ny]) {
                    d[nx][ny] = f.v + 1;
                    q.push({d[nx][ny], 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;
    }
};
lizimu0709 commented 2 years ago

思路 把所有的 陆地（1） 添加到队列中，进行广度优先遍历，看看多少步可以扩散完成

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int maxDistance(int[][] grid) {
        // 方向向量
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // 由于题目中给出了 grid 的范围，因此不用做输入检查
        int N = grid.length;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    // 把陆地添加到队列中
                    queue.add(getIndex(i, j, N));
                }
            }
        }

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

        boolean[][] visited = new boolean[N][N];
        int step = 0;
        while (!queue.isEmpty()) {
            // 注意：先把当前队列的长度保存下来
            int currentQueueSize = queue.size();
            for (int i = 0; i < currentQueueSize; i++) {
                Integer head = queue.poll();
                int currentX = head / N;
                int currentY = head % N;

                for (int[] direction : directions) {
                    int newX = currentX + direction[0];
                    int newY = currentY + direction[1];
                    if (inArea(newX, newY, N) && !visited[newX][newY] && grid[newX][newY] == 0) {
                        // 赋值成为一个不等于 0 的整数均可，因为后续逻辑只关心海洋（0）
                        visited[newX][newY] = true;
                        queue.add(getIndex(newX, newY, N));
                    }
                }
            }
            step++;
        }
        // 注意：由于最后一步，没有可以扩散的的区域，但是 step 加了 1，故在退出循环的时候应该减 1
        return step - 1;
    }

    private int getIndex(int x, int y, int cols) {
        return x * cols + y;
    }

    private boolean inArea(int x, int y, int N) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}

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

Orangejuz commented 2 years ago 

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

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

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

LQyt2012 commented 2 years ago

思路

多源BFS

代码

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        land = [[x, y] for x in range(N) for y in range(N) if grid[x][y]]
        if len(land) == 0 or len(land) == N*N:
            return -1

        length = -1
        def is_valid(x, y):
            return -1<x<N and -1<y<N

        while land:
            length += 1
            new_start = []
            for x, y in land:
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx, ny = x+dx, y+dy
                    if is_valid(nx, ny) and grid[nx][ny] == 0:
                        grid[nx][ny] = 2
                        new_start.append([nx, ny])
            land = new_start
        return length
func maxDistance(grid [][]int) int {
    N := len(grid)
    land := [][2]int{}
    for i := range grid {
        for j:= range grid[0] {
            if grid[i][j] == 1 {
                land = append(land, [2]int{i, j})
            }
        }
    }
    if len(land) == 0 || len(land) == N*N {
        return -1
    }
    length := -1
    for len(land) > 0 {
        length++
        newStart := [][2]int{}
        for i := range land {
            for _, val := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
                nx, ny := land[i][0]+val[0], land[i][1]+val[1]
                if isValid(nx, ny, N) && grid[nx][ny] == 0 {
                    grid[nx][ny] = 2
                    newStart = append(newStart, [2]int{nx, ny})
                }
            }
        }
        land = newStart        
    }
    return length
}

func isValid(x, y, N int) bool {
    return -1 < x && x < N && -1 < y && y < N
}

复杂度分析

时间复杂度分析：O(N^2)
空间复杂度分析：O(1)

hyh331 commented 2 years ago

Day51 思路

多源BFS

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

复杂度分析

VictorHuang99 commented 2 years ago

思路：动态规划 Code: ···

var maxDistance = function (grid) { 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
}

}; ··· 时间复杂度：O(N^2) 空间复杂度：O(N^2)

MoonLee001 commented 2 years ago

思路

多源BFS

代码

var maxDistance = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let res = -1;
    let q = [];

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

    if (q.length == 0 || q.length == m * n) {
        return res;
    }

    while(q.length) {
        const len = q.length;
        for (let i = 0; i < len; i++) {
            const cur = q.shift();
            for (let j = 0; j < 4; j++) {
                const nx = direction[j][0] + cur[0];
                const ny = direction[j][1] + cur[1];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 1){
                    continue;
                }
                //如果是海洋，标记为陆地，加入到队列中，距离＋1
                if (grid[nx][ny] == 0)  {
                    grid[nx][ny] = 1;
                    q.push([nx, ny]);
                }
            }
        }
        res++;
    }
    return res;

复杂度分析

miss1 commented 2 years ago

代码

var maxDistance = function(grid) {
    let m = grid.length, n = grid[0].length;
    let directions = [[1,0],[-1,0],[0,1],[0,-1]];
    let visited = new Array(m).fill(null).map(el => new Array(n).fill(false));
    let queue = [];

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

    let d = 0;
    while(queue.length){
        let size = queue.length;
        d++;

        for(let i = 0; i < size; i++){
            let [r,c] = queue.shift();
            for(let [x,y]  of directions){
                let nr = r+x, nc = c+y;

                if(!isValid(nr, nc)) continue;
                queue.push([nr,nc])
                grid[nr][nc] += d;
            }
        }
    }

    function isValid(r, c){
        if(r < 0 || c < 0 || r >= m || c >= n) return false;
        if(visited[r][c]) return false;
        if(grid[r][c] !== 0) return false;

        return true;
    }

    let max = -Infinity;
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] > max && grid[i][j] !== 0 && grid[i][j] !== 1){
                max = grid[i][j]
            }
        }
    }

    return max === -Infinity ? -1 : max;
};
flyzenr commented 2 years ago
freedom0123 commented 2 years ago 

class Solution {
    int n;
    int[][] grid;
    public int maxDistance(int[][] _grid) {
        grid = _grid;
        n = grid.length;
        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, bfs(i, j));
                }
            }
        }
        return ans;
    }
    // 单次 BFS：求解海洋位置 (x,y) 最近的陆地距离
    int bfs(int x, int y) {
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        Deque<int[]> d = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        d.addLast(new int[]{x, y});
        map.put(x * n + y, 0);
        while (!d.isEmpty()) {
            int[] poll = d.pollFirst();
            int dx = poll[0], dy = poll[1];
            int step = map.get(dx * n + dy);
            if (grid[dx][dy] == 1) return step;
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                int key = nx * n + ny;
                if (map.containsKey(key)) continue;
                d.addLast(new int[]{nx, ny});
                map.put(key, step + 1);
            }
        }
        return -1;
    } 
}
```java
revisegoal commented 2 years ago

多源bfs

mo660 commented 2 years ago

BFS

class Solution {
    const int dx[4] = {0,1,0,-1};
    const int dy[4] = {1,0,-1,0};
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int ans = -1;
        vector<vector<int>> dis(n,vector<int>(n,1000));
        queue<pair<int,int>>q;
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                if (1 == grid[i][j]){
                    q.push(make_pair(i,j));
                    dis[i][j] = 0;
                }
            }
        }
        if (q.empty()) return ans;
        while(!q.empty()){
            auto top = q.front();
            q.pop();
            for (int i = 0; i < 4; i++){
                int newX = top.first + dx[i], newY = top.second + dy[i];
                if (newX<0 || newX>=n || newY<0 ||newY>=n)
                    continue;
                if (dis[newX][newY] > 1+dis[top.first][top.second]){
                    q.push(make_pair(newX,newY));
                    dis[newX][newY] = 1+dis[top.first][top.second];
                }
            }
        }
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                if (grid[i][j] == 0 && dis[i][j]<200) {
                    ans = max(ans,dis[i][j]);
                }
            }
        }
        return ans;
    }
};
tensorstart commented 2 years ago

思路

bfs 遍历所有陆地，加入队列向外扩散，可以记住海洋对这个扩散陆地的距离，也可以直接标记+1

代码

``javascript var maxDistance = function(grid) { let dx=[0,0,1,-1]; let dy=[1,-1,0,0]; let queue=[]; let m=grid.length,n=grid[0].length; // 先把所有的陆地都入队。 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j]===1) queue.unshift([i,j]); } } // 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。 let hasOcean=false; let point=[] while (queue.length){ point=queue.pop(); let x=point[0],y=point[1]; // 取出队列的元素，将其四周的海洋入队。 for (let i = 0; i < 4; i++) { let newX=x+dx[i]; let 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.unshift([newX,newY]); } } // 没有陆地或者没有海洋，返回-1。 if (point.length===0 || !hasOcean) { return -1; } // 返回最后一次遍历到的海洋的距离。 return grid[point[0]][point[1]] - 1; };


## 复杂度分析
时间$O(n^2)$
空间$O(n)$
wychmod commented 2 years ago

思路

bfs

代码

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

        return step

复杂度

时间复杂度 On^2 空间复杂度 On^2

taojin1992 commented 2 years ago 
/*
# Logic:

BFS from each water cell, keep track of the max distance - duplicate work

BFS from each land cell instead

# Complexity:
Time:O(m*n), worst case, m = grid.length, n = grid[0].length
O(n^2)

Space: for the queue, worst O(m*n), O(n^2) specified in constraints

// [[1,0],[0,1]] ->1
// [[1,0],[0,0]] -> 2

Queue:(0,0)

size = 1
queue:(0,1),(1,0)
max=0

size = 2
queue:(1,1)
max = 1

size = 1
queue, empty
max = 2

*/

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        if (grid == null || n == 0) return -1;
        int maxDist = -1;
        Queue<int[]> nodeQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    nodeQueue.offer(new int[]{i, j});
                }
            }
        }
        // no water/no land
        if (nodeQueue.size() == 0 || nodeQueue.size() == n * n) 
            return -1;
        // bfs
        while (!nodeQueue.isEmpty()) {
                int size = nodeQueue.size();
                for (int k = 0; k < size; k++) {
                    int[] cur = nodeQueue.poll();
                    int curRow = cur[0];
                    int curCol = cur[1];
                    if (curRow - 1 >= 0 && grid[curRow-1][curCol] == 0) {
                        nodeQueue.add(new int[]{curRow-1,curCol});
                        // mark visited
                        grid[curRow-1][curCol] = -1;
                    }
                    if (curRow + 1 < grid.length && grid[curRow+1][curCol] == 0) {
                        nodeQueue.add(new int[]{curRow+1,curCol});
                        // mark visited
                        grid[curRow+1][curCol] = -1;
                    }
                    if (curCol - 1 >= 0 && grid[curRow][curCol - 1] == 0) {
                        nodeQueue.add(new int[]{curRow,curCol - 1});
                        // mark visited
                        grid[curRow][curCol - 1] = -1;
                    }
                    if (curCol + 1 < grid[0].length && grid[curRow][curCol + 1] == 0) {
                        nodeQueue.add(new int[]{curRow,curCol + 1});
                        // mark visited
                        grid[curRow][curCol + 1] = -1;
                    }
                }
                maxDist++;
        }

        return maxDist;
    }
}
carterrr commented 2 years ago

class Solution { // 本题是典型的多源头bfs 和单bfs区别是 队列开始就有一系列点 而不是1个点 // 技巧 使用grid[x][y] 是否等于 0 判断是否被访问过以及是否是陆地

final int[][] moves = new int[][] {{1,0},{-1,0},{0,1},{0,-1}};
public int maxDistance(int[][] grid) {
    int max = -1, n = grid.length;
    Queue<int[]> queue = new LinkedList<>();
    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}); // 也可使用状态压缩 比如 i* n + j  https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/yan-du-you-xian-bian-li-java-by-liweiwei1419/
            }
        }
    }

    if(queue.size() == 0 || queue.size() == n * n ) return -1; // 只有陆地或者海洋
    int[] cur = null;
    while(!queue.isEmpty()) {
        cur = queue.poll();
        for(int i = 0 ; i< 4 ;i++) {  // 遍历其他的海洋  遇到陆地或者被遍历过的海洋就跳过
            int nextX = cur[0] + moves[i][0];
            int nextY = cur[1] + moves[i][1];
            if( nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || grid[nextX][nextY] > 0) continue; // grid[nextX][nextY] > 0 表示陆地点或者是已经被其他到这个海洋点更近的陆地点bfs访问过   题目中 ： 这个海洋单元格到离它最近的陆地单元格的距离是最大
            grid[nextX][nextY] = grid[cur[0]][cur[1]] + 1; // 传播的过程 + 1
            queue.offer(new int[]{nextX, nextY});
        } 

    }
    return grid[cur[0]][cur[1]] - 1;   // 距离包含了陆地的1
}

}

sallyrubyjade commented 2 years ago 
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    let n = grid.length;
    let dp = new Array(n);
    for(let i = 0; i < n; i++) dp[i] = new Array(n).fill(0);

    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 0) dp[i][j] = Infinity;
        }

    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++) {
            if(dp[i][j] === 0) 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(dp[i][j] === 0) 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 = 0;

    for( let i = 0; i < n; i++)
        for(let j = 0; j < n; j++) {
            ans = Math.max(ans, dp[i][j]);
        }

    if(ans === Infinity || ans === 0) return - 1;
    return ans;
};
XXjo commented 2 years ago

思路

首先将陆地入队列，各个陆地同时一层一层向海洋扩散（DFS），那么最后扩散到的海洋就是最远的海洋。并且这个海洋肯定是被离他最近的陆地给扩散到的

代码

var maxDistance = function(grid) {
    let queue = [];
    let n = grid.length;
    //将所有陆地入队列
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1){
                queue.push([i, j]);
            }
        }
    }

    //DFS
    let distance = -1;
    let hasOcean = false;
    while(queue.length > 0){
        let queueLength = queue.length;
        for(let i = 0; i < queueLength; i++){
            let p = queue.shift();
            let arround = [[p[0] - 1, p[1]], [p[0] + 1, p[1]], [p[0], p[1] - 1], [p[0], p[1] + 1]];
            arround.forEach(ele => {
                if(ele[0] >= 0 && ele[0] < n && ele[1] >= 0 && ele[1] < n && grid[ele[0]][ele[1]] === 0){
                    queue.push(ele);
                    grid[ele[0]][ele[1]] = -1; //遍历过的节点置为-1，就无需使用数组表示已经访问
                    hasOcean = true;
                }
            })
        }
        distance += 1;
    }
    return hasOcean ? distance : -1;
};

复杂度分析

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

maggiexie00 commented 2 years ago 
def maxDistance(self, grid: List[List[int]]) -> int:
    q=deque()
    n=len(grid)
    for i in range(n):
        for j in range(n):
            if grid[i][j]==1:
                q.append((i,j))
    if len(q)==n*n:return -1
    dist=-1
    while q:
        dist+=1
        for _ in range(len(q)):
            x,y=q.popleft()

            for i,j in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
                if 0<=i<n and 0<=j<n and grid[i][j]==0:
                    q.append((i,j))
                    grid[i][j]=1

    return dist
houyanlu commented 2 years ago

思路

BFS 我们找出所有陆地格子，将它们放入队列，作为第 0 层的结点 然后进行 BFS 遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点 遍历结束时，当前的遍历层数就是海洋格子到陆地格子的最远距离

为了在遍历中不重复访问海洋格子，我们将已经遍历过的海洋格子的值改为 2，和原来海洋格子里的 0 区别开来

代码


class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();

        deque<pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.push_back({i, j});
                }
            }
        }

       // 如果我们的地图上只有陆地或者海洋，请返回 -1。
        if (q.empty() || q.size() == n * n) {
            return -1;
        }

        int distance = -1;
        while (!q.empty()) {
            distance++;
            int qsize = q.size();
            for (int i = 0; i < qsize; i++) {
                auto pos = q.front(); 
                q.pop_front();
                int x = pos.first;
                int y = pos.second;
                //上
                if (x - 1 >= 0 && grid[x - 1][y] == 0) {
                    grid[x - 1][y] = 2;
                    q.push_back({x - 1, y});
                }
                //下
                if (x + 1 < n && grid[x + 1][y] == 0) {
                    grid[x + 1][y] = 2;
                    q.push_back({x + 1, y});
                }
                //左
                if (y - 1 >= 0 && grid[x][y - 1] == 0) {
                    grid[x][y - 1] = 2;
                    q.push_back({x, y - 1});
                }
                //右
                if (y + 1 < n && grid[x][y + 1] == 0) {
                    grid[x][y + 1] = 2;
                    q.push_back({x, y + 1});
                }
            }
        }

        return distance;
    }
};

复杂度分析

zhishinaigai commented 2 years ago

我抄


class Solution {
public:
    static constexpr int MAX_N = 100 + 5;
    static constexpr int INF = int(1E6);

    int f[MAX_N][MAX_N];
    int n;

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

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j] = (a[i][j] ? 0 : INF);
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (a[i][j]) {
                    continue;
                }
                if (i - 1 >= 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    f[i][j] = min(f[i][j], f[i][j - 1] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (a[i][j]) {
                    continue;
                }
                if (i + 1 < n) {
                    f[i][j] = min(f[i][j], f[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    f[i][j] = min(f[i][j], f[i][j + 1] + 1);
                }
            }
        }

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

        if (ans == INF) {
            return -1;
        } else {
            return ans;
        }
    }
};
zhiyuanpeng commented 2 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = collections.deque([(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 1])
        step = -1
        if len(q) == 0 or len(q) == len(grid)*len(grid):
            return step
        while len(q):
            for i in range(len(q)):
                x, y = q.popleft()
                bfs = [(x+1, y), (x-1, y), (x, y-1), (x, y+1)]
                for xx, yy in bfs:
                    if 0 <= xx < n and 0 <= yy < n and grid[xx][yy] == 0:
                        q.append((xx, yy))
                        grid[xx][yy] = -1
            step += 1
        return step

time O(N**2) space O(N**2)

gitbingsun commented 2 years ago

class Solution { int dir[5] = {0, 1, 0, -1, 0};

public: int maxDistance(vector<vector>& grid) { int n = grid.size(); set visited; int res = 0; queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { q.push({i,j}); string str = to_string(i)+","+to_string(j); visited.insert(str); } } }

    // BFS
    int steps = -1;
    while (!q.empty()) {
        steps++;
        int qsize = q.size();
        //cout<<"qsize:"<<qsize<<endl;
        for (int i = 0; i < qsize; i++) {
            auto index = q.front(); q.pop();
            int x = index.first;
            int y = index.second;
            string str = to_string(x)+","+to_string(y);
            visited.insert(str);
            //cout<<x<<' '<<y<<' '<<steps<<endl;
            for (int j = 0; j < 4; j++) {
                int newx = x+dir[j];
                int newy = y+dir[j+1];

                if (newx<0 ||newx >=n||newy<0||newy>=n||grid[newx][newy]==1)
                    continue;
                string str = to_string(newx)+","+to_string(newy); 
                if (visited.find(str)== visited.end()) {
                    //cout<<"neighbor:"<<newx<<';'<<newy<<' '<<endl;
                    q.push({newx,newy});
                }
            }
        }
    }

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

};

gitbingsun commented 2 years ago

题目地址(1162. 地图分析)

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

题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

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

 

示例 1：

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

示例 2：

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

 

提示：

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

前置知识

BFS, 从陆地开始一层层找0， 每一层step + 1

class Solution { int dir[5] = {0, 1, 0, -1, 0};

public: int maxDistance(vector<vector>& grid) { int n = grid.size(); set visited; int res = 0; queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { q.push({i,j}); string str = to_string(i)+","+to_string(j); visited.insert(str); } } }

    // BFS
    int steps = -1;
    int x, y, newx, newy;
    while (!q.empty()) {
        steps++;
        int qsize = q.size();
        for (int i = 0; i < qsize; i++) {
            auto index = q.front(); q.pop();
            x = index.first;
            y = index.second;

            for (int j = 0; j < 4; j++) {
                newx = x+dir[j];
                newy = y+dir[j+1];
                if (newx<0 ||newx >=n||newy<0||newy>=n||grid[newx][newy]==1)
                    continue;
                string str = to_string(newx)+","+to_string(newy); 
                if (visited.find(str)== visited.end()) {
                    q.push({newx,newy});
                    visited.insert(str);
                }
            }
        }
    }

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

};



**复杂度分析**

令 n 为数组长度。

- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$