算法原理：

解法一：暴力求解。每个位置都用一次bfs计算出到最近0的距离，这毫无疑问会超时。

解法二：多源bfs+正难则反。
把所有的0当成起点，1当成终点。先把所有的0位置加入到队列中，再一层一层扩展即可。同时要创建一个与原矩阵等规模的dist矩阵，用来记录距离。

细节/技巧问题：

我们可以回想一下在解决单源最短路问题时，我们定义了一个bool类型的数组vis用来标记该位置是否被遍历过，最少步数step表示扩展层数，每次出队列的个数sz。

但是在这个问题中，我们创建的dist矩阵完全可以代替这三个东西，首先把dist矩阵初始化为-1，当dist矩阵的某一位置等于-1，说明原矩阵mat的对应位置没有标记过，当dist的某一位置不为-1，此时该位置记录的就是最近距离，并且原矩阵mat的对应位置标记过。

对于step和sz变量的作用，dist也可以代替。因为我们是从坐标[a, b] – > [x,y]进行搜索的，而dist[a,b]记录的等同于就是对应的层数。

代码实现：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m = mat.size(), n = mat[0].size();// dist[i][j] == -1：mat[i][j]位置没有标记过// dist[i][j] ！= -1：最短路vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;// 把0源点入队列for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(mat[i][j] == 0){q.push({i, j});dist[i][j] = 0;}while(q.size()){auto[a, b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){q.push({x, y});dist[x][y] = dist[a][b] + 1;}}}return dist;}
};

当然，也可以使用"土方法"解决，这里也给出代码：

class Solution
{int m, n;int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 };
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat){m = mat.size(), n = mat[0].size();vector<vector<int>> dist(m, vector<int>(n)); // 距离矩阵vector<vector<bool>> vis(m, vector<bool>(n)); // 标记矩阵queue<pair<int, int>> q;// 把所有的0入队列for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (mat[i][j] == 0){q.push({ i, j });vis[i][j] = true;}}}int step = 0;while (q.size()){step++;int sz = q.size();while (sz--){auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]){dist[x][y] = step;q.push({ x, y });vis[x][y] = true;}}}}return dist;}
};

算法原理：

这道题目可以抽象成多源bfs问题。不直接统计有多少被包围的陆地，正难则反，我们从边界上的陆地(1)做突破口。把所有边界上的1都入队列，再使用多源bfs进行搜索标记，最后再遍历一遍原数组，统计出没有标记的陆地数量即可。

细节/技巧问题：

参考前文

代码实现：

class Solution 
{bool vis[501][501];int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:int numEnclaves(vector<vector<int>>& grid) {queue<pair<int, int>> q;// 把所有边界上的1入队列int m = grid.size(), n = grid[0].size();for(int i = 0; i < m; i++){if(grid[i][0] == 1) q.push({i, 0}), vis[i][0] = true;if(grid[i][n-1] == 1) q.push({i, n-1}),vis[i][n-1] = true;}for(int j = 0; j < n; j++){if(grid[0][j] == 1) q.push({0, j}), vis[0][j] = true;if(grid[m-1][j] == 1) q.push({m-1, j}), vis[m-1][j] = true;}// 用多源bfs进行搜索标记while(q.size()){auto[a,b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){q.push({x, y});vis[x][y] = 2;}}}// 最后遍历原矩阵，根据标记数组，统计陆地数量int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 1 && !vis[i][j])ret++;return ret;}
};

算法原理：

这道题完完全全就是第一题的变式题。本题只能根据水域高度推陆地高度，所以可以使用多源bfs把所有水域位置当成"超级源点"入队列，再一层一层向外扩展。代码的实现也几乎一模一样。

细节/技巧问题：

参考第一题

代码实现：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int m = isWater.size(), n = isWater[0].size();vector<vector<bool>> vis(m, vector<bool>(n)); // 标记矩阵vector<vector<int>> hight(m, vector<int>(n)); // 高度矩阵queue<pair<int, int>> q;// 把所有水域入队列，搞定置为0for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(isWater[i][j] == 1){q.push({i, j});vis[i][j] = true;hight[i][j] = 0; // 水域的高度为0}// 使用多源bfs进行标记统计while(q.size()){auto[a, b] = q.front();q.pop();for(int k = 0; k < 4 ; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]){hight[x][y] = hight[a][b] + 1;q.push({x, y});vis[x][y] = true;}}}return hight;}
};

算法原理：

这道题也是第一题的变式题。我们把所有的陆地看成起点入队列，再使用多源bfs向外一层一层扩展。

细节/技巧问题：

参考第一题

代码实现：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:int maxDistance(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;for(int i = 0; i < m; i++)for(int j= 0; j < n; j++)if(grid[i][j] == 1){// 所以陆地入队列，距离是0q.push({i, j});dist[i][j] = 0;}int ret = -1;while(q.size()){auto[a, b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){q.push({x, y});dist[x][y] = dist[a][b] + 1;ret = max(ret, dist[x][y]); // 更新出最大结果}}}return ret;// 下面是另一种更新出最大值的方式//int ret = 0;//int sum = 0;//for(int i = 0; i < m; i++)//    for(int j = 0; j < n; j++)//    {//        sum += dist[i][j];//        if(dist[i][j] >= ret)//            ret = dist[i][j];//    }//return (sum == 0 || sum == -m*n) ? -1 : ret;}
};