【优选算法】（第四十四篇）
目录
⻜地的数量（medium）
题目解析
讲解算法原理
编写代码
地图中的最⾼点（medium）
题目解析
讲解算法原理
编写代码
⻜地的数量（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⼤⼩为 m x n 的⼆进制矩阵 grid ，其中 0 表⽰⼀个海洋单元格、 1 表⽰⼀个陆地单元格。
⼀次移动是指从⼀个陆地单元格⾛到另⼀个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回⽹格中⽆法在任意次数的移动中离开⽹格边界的陆地单元格的数量。
⽰例1：
输⼊：grid=[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个1被0包围。⼀个1没有被包围，因为它在边界上。
⽰例2：
输⼊：grid=[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有1都在边界上或可以到达边界。
提⽰：
◦ m == grid.length
◦ n == grid[i].length
◦ 1 <= m, n <= 500
◦ grid[i][j] 的值为 0 或 1
讲解算法原理
解法：
算法思路：
正难则反：
从边上的 1 开始搜索，把与边上 1 相连的联通区域全部标记⼀下；然后再遍历⼀遍矩阵，看看哪些位置的 1 没有被标记即可
标记的时候，可以⽤「多源 bfs 」解决。
编写代码
c++算法代码：
class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:int numEnclaves(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<bool>> vis(m, vector<bool>(n));queue<pair<int, int>> q;// 1. 把边上的 1 加⼊到队列中for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(i == 0 || i == m - 1 || j == 0 || j == n - 1){if(grid[i][j] == 1){q.push({i, j});vis[i][j] = true;}}// 2. 多源 bfswhile(q.size()){auto [a, b] = q.front();q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
!vis[x][y]){vis[x][y] = true;q.push({x, y});}}}// 3. 统计结果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;}
};java算法代码：
class Solution
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;boolean[][] vis = new boolean[m][n];Queue<int[]> q = new LinkedList<>();// 1. 把边上的 1 全部加⼊到队列中for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(i == 0 || i == m - 1 || j == 0 || j == n - 1){if(grid[i][j] == 1){q.add(new int[]{i, j});vis[i][j] = true;}}// 2. 多源 bfswhile(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
!vis[x][y]){q.add(new int[]{x, y});vis[x][y] = true;}}}// 3. 提取结果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;}
}地图中的最⾼点（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⼤⼩为 m x n 的整数矩阵 isWater ，它代表了⼀个由陆地和⽔域单元格组成的地图。
• 如果 isWater[i][j] == 0 ，格⼦ (i, j) 是⼀个陆地格⼦。
• 如果 isWater[i][j] == 1 ，格⼦ (i, j) 是⼀个⽔域格⼦。
你需要按照如下规则给每个单元格安排⾼度：
• 每个格⼦的⾼度都必须是⾮负的。
• 如果⼀个格⼦是⽔域，那么它的⾼度必须为 0 。
• 任意相邻的格⼦⾼度差⾄多为 1 。当两个格⼦在正东、南、西、北⽅向上相互紧挨着，就称它
们为相邻的格⼦。（也就是说它们有⼀条公共边）
找到⼀种安排⾼度的⽅案，使得矩阵中的最⾼⾼度值最⼤。
请你返回⼀个⼤⼩为 m x n 的整数矩阵 height ，其中 height[i][j] 是格⼦ (i, j) 的⾼度。如果有多种解法，请返回任意⼀个。
⽰例1：
输⼊：isWater=[[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展⽰了给各个格⼦安排的⾼度。蓝⾊格⼦是⽔域格，绿⾊格⼦是陆地格。
⽰例2：
输⼊：isWater=[[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排⽅案中，最⾼可⾏⾼度为2。任意安排⽅案中，只要最⾼⾼度为2且符合上述规则的，都为可⾏⽅案。
提⽰：
◦ m == isWater.length
◦ n == isWater[i].length
◦ 1 <= m, n <= 1000
◦ isWater[i][j] 要么是 0 ，要么是 1 。◦ ⾄少有1个⽔域格⼦。
讲解算法原理
解法：
算法思路：
01矩阵的变型题，直接⽤多源bfs解决即可。
编写代码
c++算法代码：
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<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;// 1. 把所有的源点加⼊到队列⾥⾯for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(isWater[i][j]){dist[i][j] = 0;q.push({i, j});}// 2. 多源 bfswhile(q.size()){auto [a, b] = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){dist[x][y] = dist[a][b] + 1;q.push({x, y});}}}return dist;}
};java算法代码：
class Solution
{int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] dist = new int[m][n];for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();// 1. 所有的源点加⼊到队列⾥⾯for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(isWater[i][j] == 1){q.add(new int[]{i, j});dist[i][j] = 0;}// 2. 多源 bfswhile(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1){dist[x][y] = dist[a][b] + 1;q.add(new int[]{x, y});}}}return dist;}
}