【Day 51 】2024-05-28 - 1162. 地图分析

[azl397985856]

1162. 地图分析

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

 

示例 1：

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

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

提示：

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

[Martina001]

时间复杂度 O(n^4) 空间复杂度：队列大小：O(n^2)

 public int maxDistance(int[][] grid) {
        // 这个上来一看 哎暴力解法好像可以 每个0最近的1遍历一遍 求最小值，不过可能时间复杂度高了点
        // 妙：类似于310最小高度数 是一个BFS的应用题 先把1放进去，然后遍历所有的他的邻接点0 更新后再加入queue 就是一圈一圈的遍历所有1周围的0 这样每个最远的0一定是被离他最近的1遍历到的
        // 还有一种利用dijkstra求“多源最短路径”的 回头记得看一下

        // 队列中放当前坐标值
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i, j});
                }
            }
        }
        if(queue.isEmpty()){
            return -1;
        }

        boolean hasOcean = false;
        int[] finalPoint = new int[2];
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            finalPoint[0] = x;
            finalPoint[1] =y;
            int dir[][] = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for(int dirr[]:dir){
                int nx = x + dirr[0], ny = y + dirr[1];
                if(isLegal(grid,nx,ny) && grid[nx][ny] == 0){
                    hasOcean = true;
                    // 直接更新原数组 所以可以不用判断是否访问 while循环会自动结束
                   grid[nx][ny] = 1+grid[x][y];
                   // 把更新后的节点加入队列，等待下一圈的更新
                   queue.offer(new int[]{nx, ny});
                }
            }
        }
        if(!hasOcean){
            return -1;
        }
        // 队列中最后一个元素 就是距离1最近的最远0
        return grid[finalPoint[0]][finalPoint[1]] -1;
    }
    private boolean isLegal(int[][] grid, int x, int y){
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }

[lxy1108]

python3代码

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        queue = []
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    queue.append((i,j))
        if len(queue)==0 or len(queue)==n*m:
            return -1
        dist=-1
        while queue:
            print(queue)
            q_tmp = []
            dist+=1
            for x,y in queue:
                grid[x][y]=2
                if (x)>0:
                    if grid[x-1][y]==0:
                        q_tmp.append((x-1,y))
                        grid[x-1][y]=2
                if (x+1)<m:
                    if grid[x+1][y]==0:
                        q_tmp.append((x+1,y))
                        grid[x+1][y]=2
                if (y)>0:
                    if grid[x][y-1]==0:
                        q_tmp.append((x,y-1))
                        grid[x][y-1]=2
                if (y+1)<n: 
                    if grid[x][y+1]==0:
                        q_tmp.append((x,y+1))
                        grid[x][y+1]=2
            queue=q_tmp
        return dist

[Dtjk]

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

};

[zhiyuanpeng]

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