leetcode：1162. 地图分析

题目

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

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

示例 2：

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

解答 & 代码

解法一：多源 BFS

参考题解： 图的 BFS（多源 BFS）和树的 BFS 的区别：

1. 树只有一个 root，而图可以有多个源点，因此初始时需要将多个源点都入队
2. 树是有向的，因此不需要标记节点是否访问过，而对于无向图来说，还需要标记节点是否被访问过，以防止节点多次入队（节点入队前先标记为已访问）

class Solution {  
public:
    int maxDistance(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)
            return -1;
        int n = grid.size();
        queue<pair<int, int>> q;        // 队列，存储节点的坐标
        // 1. 先将所有陆地（值为 1 的节点/格子）都入队
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 1)
                    q.push(make_pair(i, j));
            }
        }
        // 如果网格全为海洋或陆地，则直接返回 -1
        if(q.size() == 0 || q.size() == n * n)
            return -1;

        pair<int, int> point = make_pair(-1, -1);
        vector<int> dx = {-1, 1, 0, 0};        // 四个方向
        vector<int> dy = {0, 0, -1, 1};
        // 2. BFS：从各个陆地开始，一层一层地向海洋扩散，每个海洋肯定都是被最近的陆地扩散到
        // 且最后扩散到的海洋，就是离陆地最远的海洋
        while(!q.empty())
        {
            point = q.front();
            q.pop();
            int row = point.first;
            int col = point.second;
            for(int i = 0; i < 4; ++i)    
            {
                int newRow = row + dx[i];
                int newCol = col + dy[i];
                if(newRow < 0 || newRow >= n || newCol < 0 || newCol >= n || grid[newRow][newCol] != 0)
                    continue;
                q.push(make_pair(newRow, newCol));
                // 直接修改原数组，因此就不需要额外的数组来标记节点是否被访问过
                // 且最终每个 grid[i][j] - 1 就代表了该位置到最近的陆地的距离
                grid[newRow][newCol] = grid[row][col] + 1;
            }
        }

        // 最后扩散到的海洋格子，就是离陆地最远的，该位置的数值 - 1 就是其离最近的陆地的距离
        return grid[point.first][point.second] - 1;
    }
};

复杂度分析：

• 时间复杂度：遍历每个格子各一次，共个格子
• 空间复杂度：队列的空间复杂度

执行结果：

执行结果：通过

执行用时：48 ms, 在所有 C++ 提交中击败了 85.77% 的用户
内存消耗：19.3 MB, 在所有 C++ 提交中击败了 59.13% 的用户

拓展：

542. 01 矩阵，基本和本题相同，题解：

解法二：动态规划 dp

参考题解：

二维动态规划：

• 动态规划数组 dp：dp[i][j] 代表作为为 (i,j) 的这一个格子到离它最近的陆地的距离
• 状态转移方程：
  • 即，状态 dp[i][j] 取决于其上、下、左、右四个方向的邻居的状态，无法只从一个方向递推
  • 因此，需要从四个角分别开始递推，分别得到位置 (i,j) 左上方、右上方、左下方、右下方距离最近的陆地的距离

• 状态初始化：对每个格子，如果为 1（陆地），则初始化为 0，否则初始化为 INF（因为后序状态转移需要去取 min）

  class Solution {  
  public:
    int maxDistance(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)
            return -1;
        int n = grid.size();
        int INF = 2 * (n - 1) + 1;
        // 动态规划：dp[i][j] 代表作为为 (i,j) 的这一个格子到离它最近的陆地的距离
        vector<vector<int>> dp(n, vector<int>(n));    
        // 初始化
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
                dp[i][j] = grid[i][j] == 1 ? 0 : INF;
        }
  
        // 从左上角开始递推，得到 (i,j) 左上角距离最近的陆地的距离
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
                if(j - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j - 1]);
            }
        }
  
        // 从右上角开始递推，得到 (i,j) 右上角距离最近的陆地的距离
        for(int i = 0; i < n; ++i)
        {
            for(int j = n - 1; j >= 0; --j)
            {
                if(i - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
                if(j + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j + 1]);
            }
        }
  
        // 从左下角开始递推，得到 (i,j) 左下角距离最近的陆地的距离
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i + 1][j]);
                if(j - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j - 1]);
            }
        }
  
        // 从右下角开始递推，得到 (i,j) 右下角距离最近的陆地的距离
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = n - 1; j >= 0; --j)
            {
                if(i + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i + 1][j]);
                if(j + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j + 1]);
            }
        }
  
        // 找 dp 值最大的
        int result = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(dp[i][j] < INF)
                    result = max(result, dp[i][j]);
            }
        }
  
        return (result == 0 || result >= INF) ? -1 : result;
    }
  };
  

  复杂度分析：

• 时间复杂度：

• 空间复杂度：

执行结果：

执行结果：通过

执行用时：64 ms, 在所有 C++ 提交中击败了 41.11% 的用户
内存消耗：17.8 MB, 在所有 C++ 提交中击败了 80.71% 的用户

优化：上面的解法要从四个角开始 4 次递推，实际上可以优化成从任一组对角开始的 2 次递推，比如只写从左上角、右下角开始递推就行了

class Solution {  
public:
    int maxDistance(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)
            return -1;
        int n = grid.size();
        int INF = 2 * (n - 1) + 1;
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
                dp[i][j] = grid[i][j] == 1 ? 0 : INF;
        }
        // 从左上角开始递推
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
                if(j - 1 >= 0)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j - 1]);
            }
        }
        // 从右下角开始递推
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = n - 1; j >= 0; --j)
            {
                if(i + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i + 1][j]);
                if(j + 1 < n)
                    dp[i][j] = min(dp[i][j], 1 + dp[i][j + 1]);
            }
        }

        int result = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(dp[i][j] < INF)
                    result = max(result, dp[i][j]);
            }
        }

        return (result == 0 || result >= INF) ? -1 : result;
    }
};

复杂度分析：

• 时间复杂度：
• 空间复杂度：

执行结果：

执行结果：通过

执行用时：72 ms, 在所有 C++ 提交中击败了 33.36% 的用户
内存消耗：17.9 MB, 在所有 C++ 提交中击败了 77.70% 的用户