1162.As Far from Land as Possible

tags: Medium,Array,DP,BFS,Matrix

1162. As Far from Land as Possible

題目描述

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

範例

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

解答

Javascript

思路：

從每個陸地出發，往水域走，做BFS紀錄距離，更新整個grid，最後取最大的。

function masDistance(grid) {
  const lands = [];
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) lands.push([i, j]);
    }
  }
  // 全部都是陸地的時候，回傳 -1
  if (lands.length === grid.length * grid[0].length) return -1;
  const isInbounds = (i, j) => i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;

  let max = 0;
  while (lands.length) {
    const [x, y] = lands.shift();
    const neighbors = [
      [x - 1, y],
      [x + 1, y],
      [x, y - 1],
      [x, y + 1],
    ];
    for (const [i, j] of neighbors) {
      if (isInbounds(i, j) && grid[i][j] === 0) {
        grid[i][j] = grid[x][y] + 1;
        lands.push([i, j]);
        max = Math.max(max, grid[i][j]);
      }
    }
  }

  return max - 1;
}

MarsgoatFeb 10, 2023

C++

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        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});
            }
        }
        int dirs[5] = {0, 1, 0, -1, 0};
        if (q.size() == n * n) return -1;
        int ans = -1;
        while (!q.empty()) {
            int num = q.size();
            for (int i = 0; i < num; i++) {
                auto [x, y] = q.front();
                q.pop();
                for (int t = 0; t < 4; t++) {
                    int cx = x + dirs[t], cy = y + dirs[t+1];
                    if (cx < 0 || cx >= n || cy < 0 || cy >= n) continue;
                    if (grid[cx][cy] == 1) continue;
                    grid[cx][cy] = 1;
                    q.push({cx, cy});
                }
            }
            ans++;
        }
        return ans;
    }
};

Yen-Chi ChenFri, Feb 10, 2023

思路

這種沒有牆組隔的擴散問題，用DP直接先一輪往右、往下走一遍，再一輪往左、往上走一遍，就可以得到了。

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) continue;
                dp[i][j] = SHRT_MAX;
                if (i > 0) dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
                if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
            }
        }
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) continue;
                if (i + 1 < n) dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);
                if (j + 1 < n) dp[i][j] = min(dp[i][j], dp[i][j+1] + 1);
                ans = max(ans, dp[i][j]);
            }
        }
        return (ans == 0 || ans == SHRT_MAX) ? -1 : ans;
    }
};

Yen-Chi ChenFri, Feb 10, 2023

Time:

$O(n^2)$
Extra Space:

$O(n^2)$

XD Feb 10, 2023

Reference

回到題目列表