Leetcode1162: 地图分析

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

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

如果网格上只有陆地或者海洋，请返回 -1。

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

#BFS
#图

从陆地块开始逐渐向海洋延伸，最后一个到达的海洋就是离陆地最远的海洋

class Solution {
public:
    vector<int> dx = {0,0,1,-1};
    vector<int> dy = {1,-1,0,0};
  //代表了方向的向量，对一个块进行上下左右的搜索
    int maxDistance(vector<vector<int>>& grid) {
            vector<vector<int>> record(grid.size(),vector<int>(grid[0].size(),0));
        queue<pair<int,int>> nodeQueue;
    
    //把陆地加入queue
    for(int i = 0; i < grid.size();i++){
        for(int j = 0; j < grid[i].size();j++){
            if(grid[i][j] == 1){
                nodeQueue.push(pair<int,int>(i,j));
            }
        }
    }
    
    pair<int,int> node = {0,0};

//    
    while(!nodeQueue.empty()){
        int size = nodeQueue.size();
        for(int i = 0; i < size;i++){
            node = nodeQueue.front();nodeQueue.pop();
            int x = node.first;
            int y = node.second;
            for(int k = 0; k < 4;k++){
                int newX = x + dx[k];
                int newY = y + dy[k];
                if(newX < 0 || newX >= grid.size()|| newY < 0||newY >= grid[0].size()||record[newX][newY] != 0 || grid[newX][newY] != 0) continue;
//判断越界，是否visit过，以及是否是海洋
                record[newX][newY] = record[x][y] + 1;
                nodeQueue.push(pair<int,int>(newX,newY));
            }
            
        }
    }
    
    if(record[node.first][node.second] == 0) return -1;
    else return record[node.first][node.second];

    }
};

注意 图中的BFS要有一个记录有无visit过的数据结构