一.542. 01 矩阵题目描述给定一个由0和1组成的矩阵mat请输出一个大小相同的矩阵其中每一个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。示例 1输入mat [[0,0,0],[0,1,0],[0,0,0]]输出[[0,0,0],[0,1,0],[0,0,0]]示例 2输入mat [[0,0,0],[0,1,0],[1,1,1]]输出[[0,0,0],[0,1,0],[1,2,1]]提示m mat.lengthn mat[i].length1 m, n 1041 m * n 104mat[i][j] is either 0 or 1.mat中至少有一个0解题思路题目让求每个1到最近的零的距离矩阵将所有0看成水龙头是水源逐层往外蔓延。最先被蔓延到的1就是最短距离蔓延到的1矩阵位置距离1并且入队再次进行bfs蔓延直到所有的1都被水蔓延到即可求出所有1到最近0的距离矩阵代码实现/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ //队列节点用来存储坐标 typedef struct { int x, y; }QNode; //四个方向 int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) { //对矩阵里每一个位置算出它到最近的 0 的最短距离最后输出距离矩阵。 //多源bfs,多个起点入队 //1.网格上下左右移动,边权为1bfs求最短路 //2.所有的0都是源头一次性全部入队 //3.逐层向外扩散每走一步距离1第一次访问到1时就是最近零的最短距离 //4.用距离矩阵res存储答案初始标记为-10的位置直接置为0并入队 //1.初始化值 int m matSize; int n matColSize[0]; *returnSize m; //分配每行每列数组 *returnColumnSizes (int*)malloc(sizeof(int) * m); for(int i 0; i m; i){ (*returnColumnSizes)[i] n; } //2.队列初始化 QNode* queue (QNode*)malloc(sizeof(QNode) * m * n); int front 0, rear 0; //遍历矩阵,所有0入队,距离置零1标记未访问-1 for(int i 0; i m; i){ for(int j 0; j n; j){ if(mat[i][j] 0){ res[i][j] 0; queue[rear] (QNode){i, j}; }else { res[i][j] -1; } } } //3.多源BFS扩散 while(front rear) { QNode cur queue[front]; int x cur.x; int y cur.y; //四个方向遍历 for(int d 0; d 4; d) { int nx x dir[d][0]; int ny y dir[d][1]; //坐标合法或者未访问 if(nx 0 nx m ny 0 ny n res[nx][ny] -1){ res[nx][ny] res[x][y] 1; queue[rear] (QNode){nx, ny}; } } } free(queue); return res; }总结多个起点同时入队适合求到最近目标点距离二.1020. 飞地的数量题目描述给你一个大小为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.lengthn grid[i].length1 m, n 500grid[i][j]的值为0或1解题思路先将边界上的岛屿找出来即先遍历四个边界将1找出利用bfs多源起点搜索逐层将连起来的1入队并标记为0找出所有“边缘陆地”将其标记为0 剩下的就是我们要找的飞地直接遍历便可找到。代码实现// 队列结构体存储坐标 i,j typedef struct { int x, y; } Point; int numEnclaves(int** grid, int gridSize, int* gridColSize) { int m gridSize; int n gridColSize[0]; // 四个方向上下左右 int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 队列最多 m*n 个点 Point* queue (Point*)malloc(sizeof(Point) * m * n); int rear 0, front 0; // 1. 多源入队四条边界所有陆地 // 左右两列 for(int i 0; i m; i){ if(grid[i][0] 1){ queue[rear] (Point){i, 0}; grid[i][0] 0;//标记为已访问 } if(grid[i][n - 1] 1){ queue[rear] (Point){i, n - 1}; grid[i][n - 1] 0; } } // 上下两行跳过左右两端已经处理 for(int j 1; j n - 1; j){ if(grid[0][j] 1){ queue[rear] (Point){0, j}; grid[0][j] 0; } if(grid[m - 1][j] 1){ queue[rear] (Point){m - 1, j}; grid[m - 1][j] 0; } } // 2. 多源 BFS while (front rear) { Point cur queue[front]; for(int i 0; i 4; i){ //四个方向搜索 int nx cur.x dir[i][0]; int ny cur.y dir[i][1]; //如果合规且是1,则加入队列标记为0 if(nx 0 nx m ny 0 ny n grid[nx][ny] 1){ queue[rear] (Point){nx, ny}; grid[nx][ny] 0; } } } // 3. 统计剩余1的数量飞地 int ans 0; for(int i 0; i m; i){ for(int j 0; j n; j){ if(grid[i][j] 1) ans; } } free(queue); return ans; }总结先找到边界的1多源bfs逐层标记最后再找飞地。三.1765. 地图中的最高点题目描述给你一个大小为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.lengthn isWater[i].length1 m, n 1000isWater[i][j]要么是0要么是1。至少有1个水域格子。解题思路将“让最高高度尽可能大”转化成“它到最近水域的最短距离”便可以从水源开始多源bfs向外层层扩散扩散之后高度1最后输出最终高度矩阵。代码实现/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ typedef struct { int x, y; }Point; int** highestPeak(int** isWater, int isWaterSize, int* isWaterColSize, int* returnSize, int** returnColumnSizes) { //将“让最高高度尽可能大”转化成“它到最近水域的最短距离” //1.初始化 int m isWaterSize; int n isWaterColSize[0]; *returnSize m; *returnColumnSizes (int*)malloc(sizeof(int) * m); //结果矩阵初始化 int** height (int**)malloc(sizeof(int*) * m); for(int i 0; i m; i){ height[i] (int*)malloc(sizeof(int) * n); memset(height[i], -1, n * sizeof(int)); (*returnColumnSizes)[i] n;//给每一行列长度赋值 } int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //2.创建队列 Point* q (Point*)malloc(sizeof(Point) * m *n);//最多m * n个点 int rear 0, front 0; //多源入队 for(int i 0; i m; i){ for(int j 0; j n; j){ if(isWater[i][j] 1){ height[i][j] 0; q[rear] (Point){i, j}; } } } //BFS扩散 while(front rear){ Point cur q[front]; int h height[cur.x][cur.y]; for(int d 0; d 4; d){ int nx cur.x dir[d][0]; int ny cur.y dir[d][1]; //未访问的陆地 if(nx 0 nx m ny 0 ny n height[nx][ny] -1){ height[nx][ny] h 1; q[rear] (Point){nx, ny}; } } } free(q); return height; }总结多源bfs将寻找最高地问题转化为寻找距离水源最远地的问题。四.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。提示n grid.lengthn grid[i].length1 n 100grid[i][j]不是0就是1解题思路和上一题几乎一样这道题是将所有陆地作为多源bfs起点逐层向外扩散每扩散一层距离dis1,最后输出maxdis即可。代码实现typedef struct { int x, y; } Point; int maxDistance(int** grid, int gridSize, int* gridColSize) { //核心思路所有陆地都是多源起点距离初始为0 //bfs逐层扩散每走一层距离1 int n gridSize; int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //dist记录最短距离-1表示未访问 int** dist (int**)malloc(N * sizeof(int*)); Point* q (Point*)malloc(n * n * sizeof(Point)); int front 0, rear 0; for (int i 0; i n; i){ dist[i] (int*)malloc(n * sizeof(int)); memset(dist[i], -1, n * sizeof(int)); for (int j 0; j n; j){ if(grid[i][j] 1) { //陆地距离0多源入队 dist[i][j] 0; q[rear] (Point){i, j}; } } } int maxDis -1; //多源BFS扩散 while(front rear){ Point cur q[front]; int x cur.x, y cur.y; int d dist[x][y]; //四个方向 for(int k 0; k 4; k){ int nx x dir[k][0]; int ny y dir[k][1]; //未访问的海洋 if(nx 0 nx n ny 0 ny n dist[nx][ny] -1){ dist[nx][ny] d 1; if(dist[nx][ny] maxDis){ maxDis dist[nx][ny]; } q[rear] (Point){nx, ny}; } } } //释放内存空间 for(int i 0; i n; i) free(dist[i]); free(dist); free(q); return maxDis; }总结所有陆地都是多源起点距离初始为0bfs逐层扩散每走一层距离1。