[TOC]

一、题目描述

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

PS：不知道你们是怎么想的，反正我当时读到这一题中文描述的时候被绕晕了。附上这一段的英文描述：
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.

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

示例 1：

1	0	1
0	0	0
1	0	1

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

示例 2：

1	0	0
0	0	0
0	0	0

输入：[[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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题方法

1. BFS（暴力法）

思路：

题意很清晰，要求找到一个海洋节点，它到最近的陆地节点的距离，是所有海洋节点中最远的。
那么对每个海洋节点，其实就是求它到陆地节点的最短距离，一个最直观的思路，必然就是枚举每一个海洋节点，利用BFS找出最短距离，然后求出所有最短距离中最大者即可。

如果将每次入队视为基本操作，最坏情况全是海洋节点，时间复杂度： $O((mn)^2)$ ，空间复杂度： $O(mn)$ 。

当然，毫无悬念的，超时。

代码：

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        auto ans = -1;
        for (auto i = 0; i < grid.size(); ++i)
            for (auto j = 0; j < grid[i].size(); ++j)
                if (grid[i][j] == 0)
                    ans = max(ans, bfs(grid, i, j));
        return ans;
    }

    int bfs(vector<vector<int>> &grid, int i, int j) {
        vector<int> r = { -1, 0, 1, 0 };
        vector<int> c = { 0, 1, 0, -1 }; 
        queue<pair<int, int>> pos;
        pos.push({i, j}); 
        while (!pos.empty()) {
            auto cur = pos.front();
            pos.pop();
            grid[cur.first][cur.second] = -1;
            for (auto k = 0; k < r.size(); ++k) {
                auto row = cur.first + r[k];
                auto col = cur.second + c[k];
                if (valid(grid, row, col)) {
                    if (grid[row][col] == 1) {
                        reset(grid);
                        return abs(row - i) + abs(col - j);
                    }
                    else if (grid[row][col] == 0)
                        pos.push({row, col});
                }
            }
        }
        reset(grid);
        return -1;
    }

    inline bool valid(const vector<vector<int>> &grid, int i, int j) {
        return -1 < i && i < grid.size() && -1 < j && j < grid[i].size();
    }

    void reset(vector<vector<int>> &grid) {
        for (auto i = 0; i < grid.size(); ++i)
            for (auto j = 0; j < grid[i].size(); ++j)
                grid[i][j] = grid[i][j] == -1 ? 0 : grid[i][j];
    }
};

2. BFS（一种设想）

思路：

解法1最主要的问题在于重复计算量太大，例如输入：

０	0	1
0	0	1
1	1	1

首先在计算 $grid[0][0]$ 时， $grid[0][1]$ 和 $grid[1][0]$ 也会入队列，进而计算出结果。然而接下来我们还会分别计算 $grid[0][1]$ 和 $grid[1][0]$ ，这里就存在了重复计算。

划重点，重复计算。一种可能想到的方法来解决重复计算，是使用DFS配合记忆化搜索，定义：
$\begin{equation} grid[i][j]= \begin{cases} 2 & \text{正在搜索} \\ 1 & \text{陆地} \\ 0 & \text{海洋} \\ -x & \text{到陆地的最近距离为x} \end{cases} \end{equation}$
看起来好像美滋滋，然并卵。DFS并不能行得通，举例：

a	b	c
d	e	f
g	h	i

如果此时正在计算 $b$ ，需要用到 $e$ ，按照DFS的思想，会去先计算 $e$ ，得到通往 $e$ 的最短距离。但如果此时， $e$ 的最短距离的路径中，包含了 $b$ 该怎么办？先有鸡还是先有蛋？

~~当然，如果有大佬有DFS的解法，我是真心希望可以不吝赐教，因为我也很好奇还有啥解法。~~
已使用动态规划解决，见解法4。

那么，接下来还有什么优化方案吗？
这里的一个设想是，既然我已经使用BFS搜索出一些节点了，我可不可以利用已经确切计算出最短距离的那些节点，作为我搜索次数的上界？
就是说，如果计算 $grid[i][j]$ 时，入队了 $grid[i-1][j]$ ，而 $grid[i-1][j]$ 已经确实计算好了距离，我们就可以用 $grid[i-1][j]$ 的值作为接下来最大的搜索层数（最坏的情况无外乎经过 $grid[i-1][j]$ 那条路径），并维护该层数（为了防止有比经过 $grid[i-1][j]$ 更短的路径）。

具体并没有测试过，性能提升是一定有的，只是不知道会有多大。

3. BFS（填海造田）

思路：

这是真的骚操作，
题目说的很清楚，

“你知道距离陆地区域最远的海洋区域是哪一个吗？”

提示都给了，到陆地的最短距离最大的那个海洋，反过来说是不是从陆地来看离得最远的那片海洋？
那我只要“填海造田”，看看直到填完最后一块海洋需要用几步，不就找到了离陆地最远的那片海洋了？

将所有陆地入队，然后每次将该陆地周围一圈的海洋变为陆地，新的陆地入队，看看多少步之后队列为空即可。

如果将每次入队视为基本操作，每个节点均需且仅需入队一次，时间复杂度： $O(mn)$ ，空间复杂度： $O(mn)$ 。

代码：

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        queue<pair<int, int>> land;
        for (auto i = 0; i < grid.size(); ++i)
            for (auto j = 0; j < grid[i].size(); ++j)
                if (grid[i][j] == 1)
                    land.push({i, j});

        if (land.empty() || land.size() == grid.size() * grid[0].size())
            return -1;

        auto ans = 0;
        const int r[] = { -1, 0, 1, 0 };
        const int c[] = { 0, 1, 0, -1 };
        queue<pair<int, int>> next;
        while (!land.empty()) {
            ans++;
            while (!land.empty()) {
                auto cur = land.front();
                land.pop();
                for (auto k = 0; k < 4; ++k) {
                    auto i = cur.first + r[k];
                    auto j = cur.second + c[k];
                    if (valid(grid, i, j) && grid[i][j] == 0) {
                        grid[i][j] = 1;
                        next.push({i, j});
                    }
                }
            }
            land.swap(next);
        }
        return ans - 1;      // 为了取消判断next是否为空的if，
                             // 令next队列为空的那一次迭代就说明没有海了，
                             // ans不应该自增
    }

    inline bool valid(const vector<vector<int>> &grid, int i, int j) {
        return -1 < i && i < grid.size() && -1 < j && j < grid[i].size();
    }
};

4. 动态规划

思路：

正如我们在解法2中考虑的那样，解法1最让人难以接受的就是重复计算了。

其实我觉得自己DFS那一段的设想还是可以的，毕竟如果我求 $grid[i][j]$ 的最短距离，一定可以通过其周围四格的最短距离推断得到，因为它们是相邻的。
但苦于先有鸡还是先有蛋，没有办法实际操作。

等等，利用周围四格来求出 $grid[i][j]$ ，怎么有点动态规划的味道？？？难道这一题可以使用动态规划来做？？？

说干就干，让我们想想到底该怎么弄。
先考虑初始条件，很明显：
$\begin{equation} dp[i][j] = \begin{cases} 0 & grid[i][j] = 1 \\ +\infty & grid[i][j] = 0 \end{cases} \end{equation}$
接下来是状态转移方程，最直观的一定是：
$dp[i][j] = min(dp[i][j],min(dp[i-1][j], dp[i][j+1], dp[i+1][j], dp[i][j-1]) + 1)$
但如果是常规扫描的话，在求解 $dp[i][j]$ 时， $dp[i][j+1]$ 和 $dp[i+1][j]$ 都还是未知的，无法使用。也许，我们可以在求解顺序上做文章？
常规扫描只能保证在求解 $dp[i][j]$ 时，已经求结果一次 $dp[i-1][j]$ 和 $dp[i][j-1]$ ，它们等价于从上往下和从左往右的最短距离。那我是不是只要再来一次从右往左和从下往上的最短距离，就可以得到最终解了？
那我如何保证在求解 $dp[i][j]$ 时， $dp[i][j+1]$ 和 $dp[i+1][j]$ 已经求出来了呢？只要从下往上、从右往左扫描 $grid$ 数组即可。

于是我们有，
第一次扫描时：
$dp[i][j] = min(dp[i][j], min(dp[i-1][j], dp[i][j-1]) + 1)$
第二次扫描时： $dp[i][j] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1]) + 1)$

时间复杂度： $O(mn)$ ，空间复杂度： $O(mn)$ 。

代码：

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        auto rows = int(grid.size());
        auto cols = int(grid[0].size());
        
        auto waters = 0;
        for (auto i = 0; i < rows; ++i)
            for (auto j = 0; j < cols; ++j)
                waters += 0 == grid[i][j] ? 1 : 0;
        if (0 == waters || rows * cols == waters)
            return -1;

        vector<vector<int>> dp(rows, vector<int>(cols, numeric_limits<int>::max() - 1));
        for (auto i = 0; i < rows; ++i) {
            for (auto j = 0; j < cols; ++j) {
                dp[i][j] = 1 == grid[i][j] ? 0 : dp[i][j];
                if (0 < i)  dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
                if (0 < j)  dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
            }
        }
        auto ans = -1;
        for (auto i = rows - 1; i > -1; --i) {
            for (auto j = cols - 1; j > -1; --j) {
                if (i < rows - 1)   dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);
                if (j < cols - 1)   dp[i][j] = min(dp[i][j], dp[i][j+1] + 1);
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

1162.地图分析

1162.地图分析

一、题目描述

二、解题方法

1. BFS（暴力法）

2. BFS（一种设想）

3. BFS（填海造田）

4. 动态规划