1162.As Far from Land as Possible
===

###### tags: `Medium`,`Array`,`DP`,`BFS`,`Matrix`

[1162. As Far from Land as Possible](https://leetcode.com/problems/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;
}

> [name=Marsgoat][time=Feb 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;
    }
};

> [name=Yen-Chi Chen][time=Fri, 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;
    }
};

> [name=Yen-Chi Chen][time=Fri, Feb 10, 2023]

Time: $O(n^2)$
Extra Space: $O(n^2)$

> [name=XD] [time= Feb 10, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)