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

0 stars 0 forks source link

【Day 51 】2024-10-04 - 1162. 地图分析 #57

Open azl397985856 opened 4 weeks ago

azl397985856 commented 4 weeks 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
huizsh commented 4 weeks 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
qiaoeve commented 4 weeks 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


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

sleepydog25 commented 4 weeks ago
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;

        // Initialize queue for BFS
        Queue<int[]> queue = new LinkedList<>();

        // Add all land cells (1s) to the queue
        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});
                }
            }
        }

        // Edge case: If no land or no water, return -1
        if (queue.size() == 0 || queue.size() == n * n) {
            return -1;
        }

        // Directions array for up, down, left, right
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        int maxDistance = -1;

        // BFS to find the maximum distance from land to water
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];

            // Explore neighbors in 4 directions
            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];

                // Check if the neighbor is within bounds and is water (0)
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 0) {
                    // Update the water cell with distance and mark as visited
                    grid[newX][newY] = grid[x][y] + 1;
                    maxDistance = Math.max(maxDistance, grid[newX][newY] - 1);
                    queue.offer(new int[] {newX, newY});
                }
            }
        }

        return maxDistance;
    }
}
Fightforcoding commented 4 weeks ago

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

        #add all land to queue
        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 -1

        direction = [(0,1), (1,0), (0,-1), (0,1)]
        max_distance = -1

        #bfs:
        while queue:
            x, y = queue.popleft()
            for dx, dy in direction:
                nx, ny = x+dx, y+dy
                if 0<= nx < n and 0<= ny < n and grid[nx][ny] == 0:
                    grid[nx][ny] = grid[x][y] + 1
                    queue.append((nx,ny))
                    max_distance = max(max_distance, grid[nx][ny])

        return max_distance - 1