刷题-地图分析

题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

分析

中等难度图数据结构的题目, 本来解题也还算顺利, 但是看到了官方题解, 写了一些比较有意思的思路, 所以记录一下.

• 最简单的暴力解法: 多次bfs, 遍历每个海洋节点, 通过bfs找到最近的陆地单元格, 然后找到这个最短距离的最大值
• 我的思路: 扩张陆地, 从全部陆地单元格出发, 用类似BFS的方式, 先找到距离陆地单元格为1的海洋单元格, 再从距离为1的海洋单元格出发找到距离为2的单元格…以此类推直到找到所有的海洋单元格. 具体实现也很简单, 就和普通的BFS差不多, 维护一个FIFO队列, 每次都从队首单元格出发向上下左右遍历, 将新遍历的单元格加入到队列中.
• 官方题解包含了多种解法, 其中让人眼前一亮的是它将问题转换为类Dijkstra问题, 这从另一个视角介绍了和我类似的思路: 我们要求陆地和所有海洋单元格的最短距离(最短路), 但Dijkstra解决的是单源最短路, 因此, 它虚构了一个超级源点, 这个超级源点到所有陆地单元格距离为0, 那么我们的问题就变成了求超级源点到其他单元格的最短路径(的最大值).

不过这题相邻节点的距离都是1, 所以用BFS即可. 当图较为复杂时, 可以参考超级源点的这种思路, 将多源最短路变为单源最短路.

题解

class Solution {
 public:
  class Node {
   public:
    int x, y;
    Node(int x, int y) : x(x), y(y) {}
    Node() {}
  };
  queue<Node> nodeQ;
  bool newOcean(Node area, vector<vector<int>>& dis, int curDis) {
    int n = dis.size();
    if (area.x >= 0 && area.x < n && area.y >= 0 && area.y < n &&
        dis[area.x][area.y] == -1) {
      dis[area.x][area.y] = curDis + 1;
      nodeQ.push(area);
      return true;
    } else
      return false;
  }

  int maxDistance(vector<vector<int>>& grid) {
    nodeQ = queue<Node>();
    int maxD = 0, n = grid.size(), cnt = 0;
    vector<vector<int>> dis(n, vector<int>(n, -1));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          nodeQ.push(Node(i, j));
          dis[i][j] = 0;
          ++cnt;
        }
      }
    }
    if (cnt == 0 || cnt == n * n) {
      return -1;
    }
    Node cur, area;
    while (cnt < n * n) {
      cur = nodeQ.front();
      nodeQ.pop();
      if (newOcean(Node(cur.x - 1, cur.y), dis, dis[cur.x][cur.y])) {
        cnt++;
      }
      if (newOcean(Node(cur.x + 1, cur.y), dis, dis[cur.x][cur.y])) {
        cnt++;
      }
      if (newOcean(Node(cur.x, cur.y - 1), dis, dis[cur.x][cur.y])) {
        cnt++;
      }
      if (newOcean(Node(cur.x, cur.y + 1), dis, dis[cur.x][cur.y])) {
        cnt++;
      }
    }
    cur = nodeQ.back();
    return dis[cur.x][cur.y];
  }
};

可优化的部分

• 多个方向, 可以用一个方向数组表示

  static constexpr int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  ...
  Node area = Node(cur.x+dx[i], cur.y+dy[i]);

• 工具类如果没有特殊的功能, 用结构体好一些, 没必要写成类

  ``` c++
  typedef struct Node {
  int x, y;
  }Node;

优化后的代码差不多, 就不放出来了