【Day 51 】2022-01-31 - 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

[KennethAlgol]

int solve(vector<vector>& graph, int target) { set visited;

queue<int> qt;
qt.push(target);

int res = 0;
while (!qt.empty()) {
    size_t size = qt.size();

    while (size--) {
        int node = qt.front();
        qt.pop();

        visited.insert(node);
        for (auto n : graph[node]) {
            if (!visited.count(n))
                qt.push(n);
            else if (n == target)
                return res + 1;
        }
    }
    ++res;
}

return -1;

}

[fornobugworld]

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

    return steps

[CodingProgrammer]

思路

BFS

代码

class Solution {
    public int maxDistance(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int res = -1;
        int[] surroundsX = new int[]{-1, 1, 0, 0};
        int[] surroundsY = new int[]{0, 0, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        // 先把陆地入队
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // 把陆地及其周围的海洋依次出队，计算离陆地最远的海洋
        int[] posCurr = null;
        boolean hasLand = false;
        while (!queue.isEmpty()) {
            posCurr = queue.poll();
            int x = posCurr[0], y = posCurr[1];
            // 找当前陆地周围的水域
            for (int i = 0; i < 4; i++) {
                int xNew = x + surroundsX[i], yNew = y + surroundsY[i];
                // 越界或者已经访问过的水域
                if (xNew < 0 || xNew >= rows || yNew < 0 || yNew >= cols || grid[xNew][yNew] != 0) continue;
                hasLand = true;
                queue.offer(new int[]{xNew, yNew});
                grid[xNew][yNew] = grid[x][y] + 1;
            }
        }

        if (posCurr == null || !hasLand) return -1;

        return grid[posCurr[0]][posCurr[1]] - 1;
    }

}

复杂度

• Time : O(N^2)
• Space : O(N^2)

[tian-pengfei]

class Solution {

    vector<vector<int>> direction = {{0,1},{0,-1},{1,0},{-1,0}};
    int n;
    deque<pair<int,int>> q;
    vector<vector<int>> flag;
public:
    int maxDistance(vector<vector<int>>& grid) {
        this->n = grid.size();
        flag.resize(n,vector<int>(n,0));

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]==1){
                    q.emplace_back(i,j);
                    flag[i][j]=1;
                }
            }
        }
        if (q.size()==n*n)return -1;
        if(q.empty())return -1;

        return maxDistance2(grid);

    }

    int maxDistance2(vector<vector<int>>& grid){
        int distance = 0;
        while (!q.empty()){
            int length  = q.size();
            for (int i = 0; i < length; ++i) {
                auto point = q.front();
                q.pop_front();
                int _x = point.first;
                int _y = point.second;
                for (auto & a : direction) {
                    int newX = _x+a[0];
                    int newY = _y+ a[1];
                    if(!isArea(newX,newY))continue;
                    if(flag[newX][newY])continue;
                    q.emplace_back(newX,newY);
                    flag[newX][newY]=1;
                }
            }
            distance++;
        }

        return distance-1;

    }

    bool  isArea(int x,int y){
        return x>=0&&x<n&&y>=0&&y<n;
    }
};

[Alfie100]

解题思路

网格中仅有 0 和 1，因此「曼哈顿距离」可简化为最短路径长度。 题目中要求 “请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。” 根据以上两点，问题可转化为：从陆地单元格出发，找到距离最远的海洋单元格。

考虑到矩阵中可能存在多个陆地，在刚开始进行 广度优先搜索（BFS） 时将所有陆地单元格加入队列中即可。

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

        n = len(grid)
        deque = collections.deque([(i,j) for i in range(n) for j in range(n) if grid[i][j]==1])     #  所有的陆地入队列
        if len(deque) == 0 or len(deque) == n*n:
            return -1

        DIRS = [(0,1),(1,0),(0,-1),(-1,0)]
        step = 0
        while deque:
            step += 1       # 最短路径长度+1
            for _ in range(len(deque)):
                i,j = deque.popleft()
                for dx,dy in DIRS:      # 上下左右遍历
                    x,y = i+dx,j+dy
                    if 0<=x<n and 0<=y<n and grid[x][y] == 0:
                        grid[x][y] = 1      # 海洋区域记为陆地区域，并以此区域开启新一轮的搜索【避免重复搜索】
                        deque.append((x,y))

        return step-1   # 特殊性：找到离陆地最远的海洋区域后，该海洋区域还会入队列，路径长度step会多加一次，因此最终结果需要 -1

复杂度分析

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

[JudyZhou95]

代码

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

        n = len(grid)
        steps = -1
        q = []

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

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

        while q:
            l = len(q)
            for _ in range(l):
                x, y = q.pop(0)

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

            steps += 1

        return steps

复杂度

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