search

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

91 天学算法第五期打卡
55 stars 14 forks source link

【Day 51 】2021-10-30 - 1162. 地图分析 #69

Open azl397985856 opened 3 years ago

azl397985856 commented 3 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
yanglr commented 3 years ago

思路:

岛屿问题系列题, 一般是用dfs或bfs。 本题, 我打算使用bfs来做。

方法: 广度优先遍历BFS

image

代码:

实现语言: C++

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

复杂度分析

kidexp commented 3 years ago

thoughts

利用BFS做组层遍历

第一层是所有的陆地，然后每一层向下一层水遍历，修改grid来来更新距离

code

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque([(i, j) for i in range(m) for j in range(n) if grid[i][j] == 1])
        level = 0
        while queue:
            queue_size = len(queue)
            level += 1
            for _ in range(queue_size):
                c_i, c_j = queue.pop()
                for delta_i, delta_j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    new_i, new_j = c_i + delta_i, c_j + delta_j
                    if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == 0:
                        # print(new_i, new_j, grid[new_i][new_j], level)
                        grid[new_i][new_j] = -level
                        queue.appendleft((new_i, new_j))
        return -min((grid[i][j] for i in range(m) for j in range(n))) or -1

complexity

Time O(mn)

Space O(mn)

yachtcoder commented 3 years ago

BFS O(MN), O(MN)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        def neighbors(x, y):
            dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]
            for d in dirs:
                nx, ny = x + d[0], y + d[1]
                if 0 <= nx < M and 0 <= ny < N:
                    yield nx, ny

        def get_distance(queue):
            visited = set([(c[1], c[2]) for c in queue])
            dist = -1
            while queue:
                dist, x, y = queue.popleft()
                for nx, ny in neighbors(x, y):
                    if (nx, ny) not in visited:
                        visited.add((nx, ny))
                        queue.append((dist+1, nx, ny))
            return dist if dist > 0 else -1
        queue = deque()
        for x in range(M):
            for y in range(N):
                if grid[x][y] == 1:
                    queue.append((0, x, y))
        return get_distance(queue)
nonevsnull commented 3 years ago

思路

AC

代码

class Solution {
    public int maxDistance(int[][] grid) {
        int max = Integer.MIN_VALUE;

        Queue<int[]> q = new LinkedList<>();

        for(int row = 0;row < grid.length;row++){
            for(int col = 0;col < grid[0].length;col++){
                if(grid[row][col] == 1){
                    q.add(new int[]{row, col});
                }
            }
        }

        if(q.size() == grid.length * grid[0].length || q.size() == 0){
            return -1;
        }

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

        while(!q.isEmpty()){
            int size = q.size();

            for(int i = 0;i < size;i++){
                int[] cur = q.poll();
                int dis = grid[cur[0]][cur[1]] + 1;

                for(int[] direction: directions){
                    int nrow = cur[0] + direction[0];
                    int ncol = cur[1] + direction[1];
                    if(nrow >= 0 && nrow < grid.length && ncol >= 0 && ncol < grid[0].length && grid[nrow][ncol] == 0){
                        grid[nrow][ncol] = dis;
                        q.add(new int[]{nrow, ncol});
                    }
                }
            }
        }

        for(int row = 0;row < grid.length;row++){
            for(int col = 0;col < grid[0].length;col++){
                max = Math.max(max, grid[row][col]);
            }
        }

        return max - 1;

    }
}

复杂度

time: O(N^2)，遍历每个cell space: O(N)

Menglin-l commented 3 years ago

用bfs来做，先把所有的陆地入队，然后按每一个陆地的四联通区域遍历海水，最后遍历到的就是最远的海水。

代码部分：

class Solution {

    public int maxDistance(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        // 遍历所有的陆地
        for (int row = 0; row < grid.length; row ++) {
            for (int col = 0; col < grid[0].length; col ++) {
                if (grid[row][col] == 1) {
                    queue.offer(new int[]{row, col});
                }
            }
        }

        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int level = 0;
        if (queue.isEmpty() || queue.size() == grid.length * grid[0].length) return -1;

        while (!queue.isEmpty()) {
            int cnt = queue.size();
            for (int i = 0; i < cnt; i ++) {
                int[] point = queue.poll();
                for (int[] dir : dirs) {
                    int newX = point[0] + dir[0];
                    int newY = point[1] + dir[1];

                    if (isValid(grid, newX, newY)) {
                        grid[newX][newY] = 1;
                        queue.offer(new int[] {newX, newY});
                    }
                }

            }
            level ++;

        }
        // 填到最后一个海水时，它也会遍历周围的海，所以返回的结果需要 - 1
        return level - 1;
    }

    public boolean isValid(int grid[][], int r, int c) {
        return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 0;
    }

}

复杂度：

Time: O(N ^ 2)

Space: O(N ^ 2)

mixtureve commented 3 years ago

思路

bfs 类似 0，1矩阵

Java Code:


class Solution {
    public int maxDistance(int[][] grid) {
         // find a water cell such that its distance to the nearest land cell is maximized
        // like (0, 1) matrix, find the shortest path to a land, keep an globalMax
        // but what if there are more than 1 point satisfy the condition?

        // offer all the initial points to queue which have values as 1
        // we need to calculated the value for all the 0's, value is the shortest path to an island
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Deque<int[]> queue = new ArrayDeque<>();
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        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});
                    visited[i][j] = true;
                }
            }
        }

        int path = 0;
        int maxPath = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];

                if (grid[x][y] == 0) {
                    if (path > maxPath) {
                        maxPath = path;
                    }
                }

                for (int[] dir: directions) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    if (isValid(newX, newY, m, n) && !visited[newX][newY]) {
                        queue.offer(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
            path += 1;
        }
        return maxPath;
    }

    private boolean isValid(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

复杂度分析

JiangyanLiNEU commented 3 years ago

Idea

// add 1s into queue for (let i=0; i<row; i++){ for (let j=0; j<col; j++){ if (grid[i][j] == 1){ queue.push([i, j]); }; }; };

// edge cases if (queue.length == 0 || queue.length == row*col){ return result; };

// do bfs const directions = [[1,0], [-1,0], [0,-1], [0,1]] while (queue.length > 0){ let length = queue.length; for (let k=0; k<length; k++){ let [i,j] = queue.shift(); for (let changes of directions){ let newI = i+changes[0]; let newJ = j+changes[1]; if (newI >= 0 && newI < row && newJ >= 0 && newJ < col){ if (grid[newI][newJ] === 0){ grid[newI][newJ] = -1; queue.push([newI, newJ]); }; }; }; }; result++; }; return result; };


#### Python Code
```Python
class Solution(object):
    def maxDistance(self, grid):
        result = 0
        queue = deque([])

        for row in range(len(grid)):
            for col in range(len(grid[row])):
                if grid[row][col] == 1:
                    queue.append((row,col))

        if len(queue) == 0 or len(queue) == len(grid)*len(grid[0]):
            return -1

        while queue:
            print(queue)
            result += 1
            for k in range(len(queue)):
                i,j = queue.popleft()
                for newI, newJ in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                    if 0<= newI <len(grid) and 0<= newJ < len(grid[0]):
                        if grid[newI][newJ] == 0:
                            queue.append((newI,newJ))
                            grid[newI][newJ] = '*'

        return result-1
~~~
biancaone commented 3 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return -1

        m, n = len(grid), len(grid[0])
        q = collections.deque()

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

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

        level = 1
        result = -1

        while q:
            for _ in range(len(q)):
                x, y = q.popleft()
                for delta_x, delta_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    next_x = x + delta_x
                    next_y = y + delta_y
                    if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
                        continue
                    if grid[next_x][next_y] == 0:
                        result = max(result, level)
                        q.append((next_x, next_y))
                        grid[next_x][next_y] = 1
            level += 1

        return result
thinkfurther commented 3 years ago

思路

只从陆地往外搜，并把本格标记为搜索过

代码

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        steps = -1
        q = collections.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
        while len(q) > 0:
            for _ in range(len(q)):
                x, y = q.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:
                        q.append((xi, yj))
                        grid[xi][yj] = -1
            steps += 1
        return steps

复杂度

时间复杂度 ：O(N*N)

空间复杂度：O(N*N)

heyqz commented 3 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque([(i, j) for i in range(m) for j in range(n) if grid[i][j] == 1])

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

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                i, j = q.popleft()
                for x, y in directions:
                    dx, dy = x + i, y + j
                    if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] == 0:
                        q.append((dx, dy))
                        grid[dx][dy] = 1

            step += 1

        return step - 1

time complexity: O(mn) space complexity: O(mn)

zhangzz2015 commented 3 years ago

思路

关键点

代码

C++ Code:


class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {

        /// min distance. Using bfs. 
        int row =grid.size(); 
        int col = grid[0].size(); 
        queue<pair<int,int>>  que; 
        for(int i=0; i< row; i++)
        {
            for(int j =0; j < col; j++)
            {
                if(grid[i][j]==1)
                {
                    que.push(make_pair(i, j)); 
                }
            }
        }
        vector<int> direction={-1,0,1,0,-1};
        int ret = -1; 
        while(que.size())
        {
            pair<int,int> topNode = que.front(); 
            que.pop(); 
            int distance = grid[topNode.first][topNode.second]; 

            for(int i = 0; i< direction.size()-1; i++)
            {
                int irow = topNode.first+direction[i]; 
                int icol = topNode.second+direction[i+1]; 
                if(irow<0||irow>=row||icol<0||icol>=col)
                    continue; 
                if(grid[irow][icol]!=0)
                    continue; 

                que.push(make_pair(irow,icol)); 
                grid[irow][icol] = distance+1; 
                ret = max(ret, distance+1); 
            }            
        }

        return ret==-1? ret: ret-1; 

    }
};
littlemoon-zh commented 3 years ago

day 51

两种方法，bfs和dp；

dp方法：

dp[i][j] = 1 + min((dp[i-1][j], dp[i][j-1]), 1 + min(dp[i+1][j], dp[i][j+1]))

最后的结果是max(dp)

class Solution:
    def maxDistance(self, g: List[List[int]]) -> int:
        n = len(g)
        dp = [[float('inf')] * n for i in range(n)]

        for i in range(n):
            for j in range(n):
                if g[i][j] == 1:
                    dp[i][j] = 0

        res = -float('inf')
        for i in range(n):
            for j in range(n):
                if dp[i][j] != 0:
                    up = dp[i-1][j] if i-1 >= 0 else float('inf')
                    left = dp[i][j-1] if j-1 >= 0 else float('inf')
                    dp[i][j] = 1 + min(up, left)

        for i in range(n-1, -1, -1):
            for j in range(n-1, -1, -1):
                if dp[i][j] != 0:
                    right = dp[i][j+1] if j+1 < n else float('inf')
                    down = dp[i+1][j] if i+1 < n else float('inf')
                    cur = 1 + min(right, down)
                    dp[i][j] = min(cur, dp[i][j])
                    res = max(res, dp[i][j])
        if res not in (float('inf'), -float('inf')):
            return res
        return -1

Time: 遍历的三次矩阵，所以复杂度是O(n^2) Space: dp矩阵 O(n^2)

BFS方法

先把所有的1入队列，然后不断扩展；不必使用visited数组，使用原始矩阵辅助即可：

class Solution:
    def maxDistance(self, g: List[List[int]]) -> int:
        n = len(g)
        q = []
        for i in range(n):
            for j in range(n):
                if g[i][j] == 1:
                    g[i][j] == -1
                    q.append((i, j))
        if len(q) == 0 or len(q) == n * n:
            return -1
        dis = 0

        while q:
            size = len(q)

            for i in range(size):
                x, y = q.pop(0)

                for dx, dy in [[-1,0], [1,0], [0,1], [0,-1]]:
                    xx = x + dx
                    yy = y + dy
                    if n > xx >= 0 and n > yy >= 0 and g[xx][yy] != -1:
                        q.append((xx, yy))
                        g[xx][yy] = -1
            dis += 1

        return dis - 1

Time: 每个点访问一遍，O(n^2) Space: q最大是n^2，所以复杂度是 O(n^2)

wangzehan123 commented 3 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：

输入：[[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

前置知识

公司

思路

关键点

代码

Java Code:


class Solution {
    private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

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

        if (grid == null || grid.length == 0) {
            return -1;
        }

        int row = grid.length;
        int col = grid[0].length;

        // 记录0到最近的1的距离
        int[][] distance = new int[row][col];
        Queue<int[]> queue = new LinkedList<>();

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == 1) {

                    for (int[] dir : directions) {
                        int x = r + dir[0];
                        int y = c + dir[1];

                        if (x < 0 || x >= row || y < 0 || y >= row || grid[x][y] == 1 || distance[x][y] != 0) {
                            continue;
                        }

                        distance[x][y] = 1;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];

            for (int[] dir : directions) {
                int x = r + dir[0];
                int y = c + dir[1];

                if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 1 || distance[x][y] != 0) {
                    continue;
                }

                distance[x][y] = distance[r][c] + 1;
                queue.offer(new int[]{x, y});
            }
        }

        int max = -1;

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == 0) {
                    max = Math.max(max, distance[r][c]);
                }
            }
        }

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

复杂度分析

令 n 为数组长度。

cicihou commented 3 years ago 

from collections import deque
from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        '''
        Q: 遍历全部海洋区域，找到某个海洋区域点，离 最近陆地 的距离是最大的
            1. 找到所有陆地的点
            2. 遍历陆地的点，每一圈陆地边上的海洋都标记为同一层
            3. 离所有陆地最远的一层海洋，就满足题目要求
            4. 一共能循环的层数，就是答案
        '''
        m = len(grid)
        n = len(grid[0])

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

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

        # If no land or water exists in the grid, return -1.
        if len(q) == m*n or len(q) == 0:
            return -1

        level = 0
        while q:
            size = len(q)
            for _ in range(size):
                i, j = q.popleft()
                for x, y in directions:
                    xi, yj = x+i, y+j
                    if 0 <= xi < m and 0 <= yj < n and grid[xi][yj] == 0:
                        q.append((xi, yj))
                        grid[xi][yj] = 1
            level += 1
        return level - 1
laofuWF commented 3 years ago 
# put every land cell into a queue
# do bfs 
# update water cell distance to its nearest land
# update max distance

# time: O(m * n)
# space: O(m * n)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        queue = []

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    queue.append((i, j))

        distance = 0
        res = -1

        # no water or no land
        if len(queue) == rows * cols or not queue:
            return res

        while queue:
            distance += 1
            curr_size = len(queue)

            for i in range(curr_size):
                x, y = queue.pop(0)

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

                    if new_x < 0 or new_x > rows - 1 or new_y < 0 or new_y > cols - 1:
                        continue
                    if grid[new_x][new_y] == 0:
                        queue.append((new_x, new_y))
                        grid[new_x][new_y] = distance
                        res = max(res, distance)

        return res
mmboxmm commented 3 years ago

思路

模版题

代码

class Solution {
    private static final int[][] ds = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public int maxDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        Queue<Pair> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.offer(new Pair(i, j));
                }
            }
        }
        if (q.size() == 0 || q.size() == m * n) return -1;

        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Pair p = q.poll();
                for (int[] d : ds) {
                    int nx = p.x + d[0], ny = p.y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        grid[nx][ny] = 1;
                        q.offer(new Pair(nx, ny));
                    }
                }
            }
            level++;
        }

        return level - 1;
    }

    private class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
WangyingxuHalo commented 3 years ago

思路:

该题目可以考虑使用BFS来做。

方法: BFS 广度优先

以陆地为起点，向四周扩散，每次向四周扩散一格。直到扩散到最后一个海洋，则到达该海洋的的距离即为最大的曼哈顿距离。

代码:

实现语言: C++ class Solution { public: int maxDistance(vector<vector>& grid) { deque<pair<int, int> > deq; int m = grid.size(); int n = grid[0].size(); 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; } grid[x][y] = 2; deq.push_back({x, y}); } } } return distance; } private: vector<vector > directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; };

复杂度分析

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

Daniel-Zheng commented 3 years ago

思路

BFS。

代码(C++)

class Solution {
public:
    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {1, 0, -1, 0};
    int maxDistance(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        vector<vector<int>> dist(grid.size(), vector(grid.size(), 1000));
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.size(); j++) {
                if (grid[i][j] == 1) {
                    q.push({i, j});
                    dist[i][j] = 0;
                }
            }
        }
        while (!q.empty()) {
            pair<int, int> 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 >= grid.size() || newY < 0 || newY >= grid.size()) continue;
                if (dist[newX][newY] > dist[top.first][top.second] + 1) {
                    dist[newX][newY] = dist[top.first][top.second] + 1;
                    q.push({newX, newY});
                }
            }
        }
        int res = -1;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.size(); j++) {
                if (grid[i][j] == 0 && dist[i][j] <= 200) res = max(res, dist[i][j]);
            }
        }
        return res;
    }
};

复杂度分析

RocJeMaintiendrai commented 3 years ago

题目

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

思路

BFS + 使用二维数组记录

代码

class Solution {
    public int maxDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dists = new int[m][n];
        for(int i = 0; i < m; i++) {
            Arrays.fill(dists[i], Integer.MAX_VALUE);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    dists[i][j] = 0;
                    bfs(i, j, grid, dists);
                }
            }
        }
        int res = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 0) res = Math.max(dists[i][j], res);
            }
        }
        if(res == Integer.MAX_VALUE || res == 0) return -1;
        return res;
    }

    private void bfs(int a, int b, int[][] grid, int[][] dists) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int[][] visited = new int[m][n];
        queue.offer(new int[]{a, b});
        visited[a][b] = 1;
        while(!queue.isEmpty()) {
            int[] cur =  queue.poll();
            int x = cur[0], y = cur[1];
            int dist = dists[x][y] + 1;
            if(x - 1 >= 0 && grid[x - 1][y] == 0 && visited[x - 1][y] == 0) {
                dists[x - 1][y] = Math.min(dists[x - 1][y], dist);
                visited[x - 1][y] = 1;
                queue.offer(new int[]{x - 1, y});
            }
            if(x + 1 < m && grid[x + 1][y] == 0 && visited[x + 1][y] == 0) {
                dists[x + 1][y] = Math.min(dists[x + 1][y], dist);
                visited[x + 1][y] = 1;
                queue.offer(new int[]{x + 1, y});
            } 
            if(y - 1 >= 0 && grid[x][y - 1] == 0 && visited[x][y - 1] == 0) {
                dists[x][y - 1] = Math.min(dists[x][y - 1], dist);
                visited[x][y - 1] = 1;
                queue.offer(new int[]{x, y - 1});
            } 
            if(y + 1 < n && grid[x][y + 1] == 0 && visited[x][y + 1] == 0) {
                dists[x][y + 1] = Math.min(dists[x][y + 1], dist);
                visited[x][y + 1] = 1;
                queue.offer(new int[]{x, y + 1});
            } 
        }
    }
}

复杂度分析

时间复杂度

O(n ^ 2)

空间复杂度

O(n ^ 2)

tongxw commented 3 years ago

思路

多源BFS，并且要记层数。

代码

class Solution {
  public int maxDistance(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    for (int i=0; i<m; i++) {
      for (int j=0; j<n; j++) {
        if (grid[i][j] == 1) {
          q.offer(new int[]{i, j});
        }
      }
    }

    int[] dx = new int[] {1, 0, -1, 0};
    int[] dy = new int[] {0, 1, 0, -1};
    int step = -1;
    boolean foundWater = false;
    while (!q.isEmpty()) {
      step++;
      int size = q.size();
      for (int i=0; i<size; i++) {
        int[] rowcol = q.poll();
        for (int k=0; k<4; k++) {
          int newRow = rowcol[0] + dx[k];
          int newCol = rowcol[1] + dy[k];

          if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0) {
            grid[newRow][newCol] = 2;
            foundWater = true;
            q.offer(new int[]{newRow, newCol});
          }

        }
      }
    }

    return foundWater ? step : -1;
  }
}

TC: O(m * n) SC: O(min(m, n))

yingliucreates commented 3 years ago

link:

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

代码 Javascript

const maxDistance = function (grid) {
  let queue = [],
    steps = 0,
    col = grid[0].length,
    row = grid.length,
    dirs = [
      [0, 1],
      [1, 0],
      [-1, 0],
      [0, -1],
    ];

  for (let i = 0; i < row; i++)
    for (let j = 0; j < col; j++) if (grid[i][j]) queue.push([i, j, 0]);

  while (queue.length) {
    steps++;
    const len = queue.length;

    for (let i = 0; i < len; i++) {
      const [x, y, dis] = queue.shift();

      for (const [xSteps, ySteps] of dirs) {
        if (grid[x + xSteps] && grid[x + xSteps][y + ySteps] === 0) {
          queue.push([x + xSteps, y + ySteps, dis + 1]);
          grid[x + xSteps][y + ySteps] = -1;
        }
      }
    }
  }

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

复杂度分析

joeytor commented 3 years ago

思路

从所有的陆地开始, 先将陆地添加入栈中

每次 visit queue 中元素的 neighbour, 然后 step += 1, 每一次 访问结束代表 queue 中的元素访问时 需要 从 某一处陆地走 step 步才能达到

访问海洋后, 进行标记, 并且将海洋的未被访问的 neighbour 添加入 queue 中进行下一轮访问

最后 返回 step, step 的大小是最后一轮能被访问到的海洋需要的步数的大小, 利用了 BFS 每次遍历最接近的一层的特性

from collections import deque

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

        m, n = len(grid), len(grid[0])

        directions = [(1,0), (0,1), (-1,0), (0,-1)]
        step = -1
        q = deque()

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

        # special case of no land or no water
        if len(q) == m*n or len(q) == 0:
            return -1

        while len(q) > 0:
            for _ in range(len(q)):
                i, j = q.popleft()
                for d1, d2 in directions:
                    i1, j1 = i+d1, j+d2
                    if i1 < 0 or i1 >= m or j1 < 0 or j1 >= n:
                        continue
                    if grid[i1][j1] != 0:
                        continue
                    q.append((i1, j1))
                    grid[i1][j1] = 1

            step += 1

        return step

复杂度

m,n 为 行 和 列 的数目

时间复杂度: O(mn) 每个节点都被访问一次

空间复杂度: O(mn) queue 的空间复杂度是 O(mn)

ZacheryCao commented 3 years ago

Idea:

BFS. The problem can be converted to finding the root whose minimum weighted edge to its nodes is maximum. The root is the cell with water, its nodes are the cells of land it can access to. The edge's weight is the Manhattan distance between the water cell and land cell. Then this is a graph problem, which can have multiple roots. For problems of searching minimum in maximum or maximum in minimum, BFS is better than DFS, since you can expand the search range a layer by a layer, from the center to the most out layer.

Code:

from collections import deque 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        stack = deque()
        seen = set()
        n = len(grid)
        if n < 1:
            return -1
        m = len(grid[0])
        if m < 1:
            return -1
        ans = -1
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    seen.add((i, j))
                    stack.append([i, j, 0])
        if len(stack) == 0 or len(stack) == m * n:
            return -1
        while stack:
            l = len(stack)
            for _ in range(l):
                i, j, c = stack.popleft()
                for h in {(-1, 0), (0, 1), (0, -1), (1,0)}:
                    ii, jj = i + h[0], j + h[1]
                    if 0 <= ii < n and 0 <= jj < m and (ii, jj) not in seen:
                        seen.add((ii, jj))
                        ans = max(ans, c + 1)
                        stack.append([ii, jj, c + 1])
        return ans

Complexity:

Time: O(N^2). You need to search all cells. Space: O(N^2). You need to store all cells in seen and stack.

xieyj17 commented 3 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = deque()
        res = 0

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

        while queue:
            for _ in range(len(queue)):
                t = queue.popleft()
                r, c = t[0]
                d = t[1]

                res = max(res, d)

                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    x = r+dr
                    y = c+dc
                    if (x<0 or x==n) or (y<0 or y==n):
                        continue

                    if grid[x][y] == 0:
                        grid[x][y] = -1
                        queue.append([(x,y), d+1])

        if res == 0:
            res = -1
        return res

Space: O(n^2)

Time: O(n^2)

Serena9 commented 3 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
ychen8777 commented 3 years ago

思路

遍历地图，以每一个水域cell为中心，用 bfs 找到离它最近的岛屿的距离，记录最大距离

代码

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

        int res = -1;

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

                if (grid[row][col] == 0) {
                    res = Math.max(res, distanceToIsland(grid, row, col));
                }

            }
        }

        return res;
    }

    private int distanceToIsland(int[][] grid, int row, int col) {

        boolean[][] visited = new boolean[grid.length][grid.length];

        int[] drow = {0, 0, 1, -1};
        int[] dcol = {1, -1, 0, 0};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{row, col, 0});
        visited[row][col] = true;

        while (!queue.isEmpty()) {
            int[] curPosition = queue.poll();
            for(int i = 0; i < 4; i++) {
                int newRow = curPosition[0] + drow[i];
                int newCol = curPosition[1] + dcol[i];

                if (!(newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid.length)){
                    continue;
                }

                if (!visited[newRow][newCol]) {
                    queue.offer(new int[]{newRow, newCol, curPosition[2] + 1});
                    visited[newRow][newCol] = true;

                    if (grid[newRow][newCol] == 1) {
                        return curPosition[2] + 1;
                    }

                } 

            }

        }

        return -1;
    }

}

复杂度

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

pophy commented 3 years ago

思路

Java Code

class Solution {
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int maxDistance(int[][] grid) {
        Queue<Point> queue = new LinkedList();
        int m = grid.length, n = grid[0].length;
        int[][] visited = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new Point(i, j));
                    visited[i][j] = 1;
                }
            }
        }
        int res = -1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point curP = queue.poll();
                for (int[] d : directions) {
                    int nX = curP.x + d[0];
                    int nY = curP.y + d[1];
                    if (nX >= 0 && nX < m && nY >= 0 && nY < n && grid[nX][nY] == 0 && visited[nX][nY] == 0) {
                        queue.add(new Point(nX, nY));
                        visited[nX][nY] = 1;
                    }
                }
            }
            res++;
        }
        return res == 0 ? -1 : res;
    }

    private static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

时间&空间

st2yang commented 3 years ago

思路

代码

复杂度

xjlgod commented 3 years ago 
class Solution {
    public int maxDistance(int[][] grid) {
        Deque<int[]> queue = new LinkedList<>();
        int N = grid.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        boolean hasOcean = false;
        int[] points = null;
        // 开始从每个点bfs
        while (!queue.isEmpty()) {
            points = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = points[0] + dx[i];
                int y = points[1] + dy[i];
                if (x < 0 || y < 0 || x >= N || y >= N || grid[x][y] != 0) {
                    continue;
                }
                hasOcean = true;
                grid[x][y] = grid[points[0]][points[1]] + 1;
                queue.add(new int[]{x, y});
            }
        }
        if (!hasOcean || points == null) {
            return -1;
        }
        return grid[points[0]][points[1]] - 1;
    }
}
Francis-xsc commented 3 years ago

思路

bfs

代码


class Solution {
private:
    struct pos{
        int x;
        int y;
        pos(int X,int Y):x(X),y(Y){}
    };
    int xd[4]={0,1,0,-1};
    int yd[4]={1,0,-1,0};
    vector<vector<bool>>visit;
public:
    int maxDistance(vector<vector<int>>& grid) {
        if(check(grid))
            return -1;
        int res=-1;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]==0){
                    int t=bfs(grid,i,j);
                    res=res>t?res:t;
                }
            }
        }
        return res;
    }
    bool check(vector<vector<int>>& grid){
        int one=0,zero=0;
        for(auto x:grid){
            for(auto y:x){
                if(zero&&one)
                    return false;
                if(y==1)one++;
                if(y==0)zero++;
            }
        }
        return true;
    }
    int bfs(vector<vector<int>> grid,int x,int y){
        int size=grid.size();
        visit=vector<vector<bool>>(size,vector<bool>(size,false));
        queue<pos*>q;
        q.push(new pos(x,y));
        while(!q.empty()){
            int frontX=q.front()->x;
            int frontY=q.front()->y;
            q.pop();
            visit[frontX][frontY]=1;
            if(grid[frontX][frontY]==1){
                return abs(x-frontX)+abs(y-frontY);
            }
            for(int i=0;i<4;i++){
                int newX=frontX+xd[i];
                int newY=frontY+yd[i];
                if(newX>=0&&newY>=0&&newX<size&&newY<size&&!visit[newX][newY]){
                    q.push(new pos(newX,newY));
                }
            }

        }
        return -1;
    }
};

复杂度分析

itsjacob commented 3 years ago

Intuition

Implementation

class Solution
{
public:
  int maxDistance(vector<vector<int>> &grid)
  {
    // find the maximum depth away from the land vertices
    // use all land as starting vertices and expand from them
    std::queue<std::pair<int, int>> aQueue;
    int n = grid.size();
    for (int jj = 0; jj < n; jj++) {
      for (int ii = 0; ii < n; ii++) {
        if (grid[jj][ii] == 0) continue;
        aQueue.push({ jj, ii });
      }
    }

    // pruning
    if (aQueue.size() == 0 || aQueue.size() == n * n) return -1;

    std::vector<std::pair<int, int>> dirs{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    int depth{ 0 };
    while (!aQueue.empty()) {
      int nsize = aQueue.size();
      depth++;
      for (int ii = 0; ii < nsize; ii++) {
        auto me = aQueue.front();
        aQueue.pop();
        // grid[me.first][me.second] = depth;
        for (auto &dir : dirs) {
          int row = me.first + dir.first;
          int col = me.second + dir.second;
          if (row < 0 || row >= n || col < 0 || col >= n || grid[row][col] != 0) continue;
          // Set the neigboring depth here to avoid adding the same neighbors from different vertices
          grid[row][col] = depth;
          aQueue.emplace(row, col);
        }
      }
    }
    return depth - 1;
  }
};

Complexity

hewenyi666 commented 3 years ago

题目名称

1162. 地图分析

题目链接

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

题目思路

参考题解

  1. 把所有陆地格子入队
  2. 处理只有陆地或者海洋的特殊情况，返回-1。
  3. 遍历所有陆地节点的周围格子，若是海洋格子则入队，且距离distance + 1
  4. 已遍历到的海洋格子置为1，避免重复计算
  5. 继续遍历已在队列中的格子的周围格子，直到没有海洋格子为止，此时队列为空，循环结束，返回distance

code for Python3

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

        distance = -1
        while queue:
            distance += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and not grid[nx][ny]:
                        grid[nx][ny] = 1
                        queue.append((nx, ny))
        return distance

复杂度分析

wenlong201807 commented 3 years ago

代码块


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

时间复杂度和空间复杂度

user1689 commented 3 years ago

题目

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

思路

单源朴素BFS, 多源朴素BFS

python3

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

        # time row * col * (row * col) = n**4
        # space row * col
        def bfs(x, y):
            queue = deque()
            visited = [[False for _ in range(col)] for _ in range(row)]
            queue.append((x, y))
            visited[x][y] = True
            step = 1
            while(queue):
                size = len(queue)
                for _ in range(size):
                    x, y = queue.popleft()
                    for new_x, new_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                        if 0<=new_x<row and 0<=new_y<col and not visited[new_x][new_y]:
                            visited[new_x][new_y] = True
                            queue.append((new_x, new_y))
                            if grid[new_x][new_y] == 1:
                                return step
                step += 1
            return -1

        row = len(grid)
        col = len(grid[0])
        maxStep = -1
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 0:
                    maxStep = max(maxStep, bfs(i, j))
        return maxStep

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

        # time n**2
        # space n**2
        # 朴素多源BFS
        row = len(grid)
        col = len(grid[0])
        queue = collections.deque()
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    queue.append((i, j))
        # corner case
        if len(queue) == 0 or len(queue) == row * col:
            return -1

        # 会多算一次 所以设置成-1 可能的解决方案：如果能写在方法里就可以提前return  
        distance = -1
        while (queue):
            size = len(queue)
            for _ in range(size):
                x, y = queue.popleft()
                for newX, newY in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if 0<=newX<row and 0<=newY<col:
                        if grid[newX][newY] != 1:
                            grid[newX][newY] = 1
                            queue.append((newX, newY))
            distance += 1
        return distance

复杂度分析

相关题目

  1. https://leetcode-cn.com/problems/max-area-of-island/
  2. https://leetcode-cn.com/problems/number-of-islands/
ghost commented 3 years ago

题目

  1. As Far from Land as Possible

思路

BFS

代码


class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        distance = 0
        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) == 0 or len(queue) == n*n : return -1
        while(queue):
            distance+=1
            for i in range(len(queue)):
                t = queue.popleft()
                for dir in [[0,1], [0,-1], [1,0], [-1,0]]:
                    x = t[0] + dir[0]
                    y = t[1] + dir[1]

                    if x<0 or x>=n or y<0 or y>=n or grid[x][y]!=0: continue

                    grid[x][y] = distance
                    queue.append([x,y])

        return distance-1

复杂度

Space: O(nn) Time: O(nn)

hellowxwworld commented 3 years ago

思路

遍历 grid 每个为 0 的 postion，并对此 position 做 bfs 搜索，拿到离该 position 曼哈顿距离最近的 val 为 1 的距离数值标为 minPer0; 遍历每个 0 拿到的 minPer0 做比较并更新 maxDistance;

代码

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

int absVal(int a, int b) {
    if (a < b)
        return b - a;
    return a - b;
}

int maxDistance(vector<vector<int>> grid) {
    int maxDistance = 0;
    int res[3] = {0};

    int m = grid.size();
    int n = grid[0].size();
    int nx, ny;
    int minPer0 = 0;
    bool visited[m][n];

    memset(visited, false, sizeof(visited));
    memset(res, -1, sizeof(res));

    queue<int> q;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!grid[i][j]) {
                memset(visited, false, sizeof(visited));
                minPer0 = m + n;
                visited[i][j] = true;
                int idx = i * n + j;
                q.push(idx);

                while (!q.empty()) {
                    idx = q.front();
                    q.pop();
                    int x = idx / n;
                    int y = idx % n;

                    for (int k = 0; k < 4; ++k) {
                        nx = x + dx[k];
                        ny = y + dy[k];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                            if (grid[nx][ny])
                                minPer0 = min(minPer0, absVal(nx, i) + absVal(ny, j));
                            else if (!visited[nx][ny]) {
                                visited[nx][ny] = true;
                                idx = nx * n + ny;
                                q.push(idx);
                            }
                        }
                    }
                }

                if (minPer0 > maxDistance) {
                    maxDistance = minPer0;
                    res[0] = i;
                    res[1] = j;
                    res[2] = maxDistance;
                }
            }
        }
    }
    // cout << "x:" << res[0] << endl;
    // cout << "y:" << res[1] << endl;
    // cout << "maxDistance:" << res[2] << endl;

    return maxDistance;
}
akxuan commented 3 years ago

思路: 这题和 count island 很像, 但是是bfs , 很好用的 queue, 每次延深一步即可. 另外我这个 helper 还是需要用的 最后, 时间空间复杂度都是 O(N)

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

        def search(grid,r,c):
            res = []
            for x,y in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                if x>= 0 and y >=0 and x <len(grid) and y< len(grid[0]) and grid[x][y] == 0:
                    res.append((x,y)) 
            return res

        #q = []

        q = deque()
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    q.append((r,c))

        res = 0

        while q:
            x, y = q.popleft()

            actions = search(grid,x, y)

            if actions:

                for temp_x, temp_y in actions:
                    grid[temp_x][temp_y] =  grid[x][y] +1 
                    res = max(res,grid[temp_x][temp_y])
                    q.append((temp_x,temp_y))

        return res -1
biscuit279 commented 3 years ago

思路：将陆地入队，遍历寻找海洋，直到边缘位置

import collections
class Solution(object):
    def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        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))
                    # print(queue)
        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）

Yufanzh commented 3 years ago

Intuition

calculate distance -- BFS

Algorithm in python 3

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        #calculate distance, use BFS
        #put all 1s to queue at the same time, and then start to do BFS for each 1
        n = len(grid)
        ans = -1
        queue = collections.deque()
        DIR = [0, 1, 0, -1, 0]
        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 ** 2:
            return ans
        while queue:
            ans += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for i in range(4):
                    xr = r + DIR[i]
                    xc = c + DIR[i+1]
                    if xr >= 0 and xr < n and xc >= 0 and xc < n and grid[xr][xc] == 0:
                        queue.append((xr, xc))
                        grid[xr][xc] = -1
            #ans += 1

        return ans

Complexity Analysis:

watermelonDrip commented 3 years ago 
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

        distance = -1
        while queue:
            distance += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and not grid[nx][ny]:
                        grid[nx][ny] = 1
                        queue.append((nx, ny))
        return distance
ai2095 commented 3 years ago

1162. As Far from Land as Possible

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

Topics

思路

Start from all islands and do BFS till reach all grid.

代码 Python

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        r_len, c_len = len(grid), len(grid[0])
        q = deque([(r, c) for r in range(r_len) for c in range(c_len) if grid[r][c] == 1])
        dist = -1
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = set(q)
        while q:
            size = len(q)
            dist += 1
            for _ in range(size):
                cur_r, cur_c = q.popleft()
                for d in directions:
                    new_r, new_c = cur_r + d[0], cur_c + d[1]
                    if 0 <= new_r < len(grid) and 0 <= new_c < len(grid[0]):
                        if (new_r, new_c) in visited:
                            continue
                        else:
                            visited.add((new_r, new_c))
                            q.append((new_r, new_c))
        return -1 if dist == 0 else dist

复杂度分析

时间复杂度： O(RC)
空间复杂度：O(RC)

learning-go123 commented 3 years ago

思路

关键点

代码

Go Code:


func maxDistance(grid [][]int) int {
    var q [][2]int
    N := len(grid)
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            if grid[i][j] == 1 {
                q = append(q, [2]int{i, j})
            }
        }
    }

    if len(q) == 0 || len(q) == N*N {
        return -1
    }

    res := -1

    for len(q) > 0 {
        size := len(q)

        for i := 0; i < size; i++ {
            x, y := q[i][0], q[i][1]
            for _, dir := range [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} {
                nx, ny := x+dir[0], y+dir[1]
                // 检查边界
                if !(nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    continue
                }

                // 判断是否之前走过
                if grid[nx][ny] > 0 {
                    continue
                }

                grid[nx][ny] = grid[x][y] + 1

                // 加入队列
                q = append(q, [2]int{nx, ny})
            }
        }

        q = q[size:]
        res++
    }

    return res
}

复杂度分析

令 n 为数组长度。

shibingchao123 commented 3 years ago

class Solution {

public int maxDistance(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    // 遍历所有的陆地
    for (int row = 0; row < grid.length; row ++) {
        for (int col = 0; col < grid[0].length; col ++) {
            if (grid[row][col] == 1) {
                queue.offer(new int[]{row, col});
            }
        }
    }

    int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int level = 0;
    if (queue.isEmpty() || queue.size() == grid.length * grid[0].length) return -1;

    while (!queue.isEmpty()) {
        int cnt = queue.size();
        for (int i = 0; i < cnt; i ++) {
            int[] point = queue.poll();
            for (int[] dir : dirs) {
                int newX = point[0] + dir[0];
                int newY = point[1] + dir[1];

                if (isValid(grid, newX, newY)) {
                    grid[newX][newY] = 1;
                    queue.offer(new int[] {newX, newY});
                }
            }

        }
        level ++;

    }
    // 填到最后一个海水时，它也会遍历周围的海，所以返回的结果需要 - 1
    return level - 1;
}

public boolean isValid(int grid[][], int r, int c) {
    return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 0;
}

} 复杂度： Time: O(N ^ 2) Space: O(N ^ 2)

Richard-LYF commented 3 years ago

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

    queue = []
    # 将所有的陆地格子加入队列
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 1:
                queue.append((i, j))
    # 如果我们的地图上只有陆地或者海洋，请返回 -1。
    if len(queue) == 0 or len(queue) == N * N:
        return -1

    distance = -1
    while len(queue) > 0:
        distance += 1
        # 这里一口气取出 n 个结点，以实现层序遍历
        n = len(queue)
        for i in range(n):
            r, c = queue.pop(0)
            # 遍历上边单元格
            if r-1 >= 0 and grid[r-1][c] == 0:
                grid[r-1][c] = 2
                queue.append((r-1, c))
            # 遍历下边单元格
            if r+1 < N and grid[r+1][c] == 0:
                grid[r+1][c] = 2
                queue.append((r+1, c))
            # 遍历左边单元格
            if c-1 >= 0 and grid[r][c-1] == 0:
                grid[r][c-1] = 2
                queue.append((r, c-1))
            # 遍历右边单元格
            if c+1 < N and grid[r][c+1] == 0:
                grid[r][c+1] = 2
                queue.append((r, c+1))

    return distance
zszs97 commented 3 years ago

开始刷题

题目简介

【Day 48 】2021-10-27 - 401. 二进制手表

题目思路

题目代码

代码块

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

复杂度

zhangyalei1026 commented 3 years ago

思路

问题为离陆地最远的海洋。把所有陆地加入queue中，找到陆地相邻的所有海洋加入queue中，直到没有合适的海洋加入，也就是找最远的海洋层。

代码

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

复杂度分析

时间复杂度：O(n2) 空间复杂度：O(n2)

Bochengwan commented 3 years ago

思路

找到所有的陆地，从陆地开始BFS，层次遍历，知道所有的海洋都被搜索。

代码

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

        dx = [1,0,-1,0]
        dy = [0,1,0,-1]

        queue_one = collections.deque()
        row = len(grid)
        col = len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == 1:
                    queue_one.append((r,c))
        n = len(queue_one)

        if n==0 or n == row*col:
            return -1
        seen = set()
        ans = -1

        while queue_one:
            n = len(queue_one)
            ans+=1

            for _ in range(n):
                x,y = queue_one.popleft()
                for i in range(4):
                    nx,ny = x+dx[i],y+dy[i]
                    if 0<=nx<row and 0<=ny<col and (nx,ny) not in seen and grid[nx][ny] == 0:
                        seen.add((nx,ny))
                        queue_one.append((nx,ny))

        return ans

复杂度分析

chang-you commented 3 years ago 
class Solution {

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

    public int maxDistance(int[][] grid) {
        int cells = grid.length * grid[0].length;
        for(int[] gr : grid)
            for(int g : gr)if(g==1)cells--;
        if(cells==grid.length * grid[0].length || cells==0)return -1;
        int it = 1;
        while(cells>0){
            for(int r = 0;r<grid.length;r++){
                for(int c=0;c<grid[r].length;c++){
                    if(grid[r][c] == it){
                        for(int[] move : moves){
                            int rT = r+move[0];
                            int cT = c+move[1];
                            if(rT<0 || cT<0 ||rT==grid.length||cT==grid[rT].length || grid[rT][cT]!=0)continue;
                            grid[rT][cT]=it+1;
                            cells--;
                        }
                    }
                }
            }
            it++;
        }
        return it-1;
    }
}
HouHao1998 commented 3 years ago

代码

class Solution {

    public int maxDistance(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        // 遍历所有的陆地
        for (int row = 0; row < grid.length; row ++) {
            for (int col = 0; col < grid[0].length; col ++) {
                if (grid[row][col] == 1) {
                    queue.offer(new int[]{row, col});
                }
            }
        }

        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int level = 0;
        if (queue.isEmpty() || queue.size() == grid.length * grid[0].length) return -1;

        while (!queue.isEmpty()) {
            int cnt = queue.size();
            for (int i = 0; i < cnt; i ++) {
                int[] point = queue.poll();
                for (int[] dir : dirs) {
                    int newX = point[0] + dir[0];
                    int newY = point[1] + dir[1];

                    if (isValid(grid, newX, newY)) {
                        grid[newX][newY] = 1;
                        queue.offer(new int[] {newX, newY});
                    }
                }

            }
            level ++;

        }
        // 填到最后一个海水时，它也会遍历周围的海，所以返回的结果需要 - 1
        return level - 1;
    }

    public boolean isValid(int grid[][], int r, int c) {
        return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 0;
    }

}

复杂度

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

RonghuanYou commented 3 years ago 
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        if not grid: return 

        queue = []        
        row, col = len(grid), len(grid[0])
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    queue.append((i, j, 0))

        res = 0
        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while queue:
            i, j, res = queue.pop(0)
            for xd, yd in d:
                x, y = i + xd, j + yd
                if row > x >= 0 and col > y >= 0 and grid[x][y] == 0:
                    grid[x][y] = 1
                    queue.append((x, y, res + 1))

        return res if res != 0 else -1