第一题
542. 01 矩阵
本题本来求解的是每一个1到0的最短距离并返回到矩阵之中；
我们采用正难则反的思路，将其化解为每一个0到每一个1的最短距离，并通过矩阵来返回；
解法：多源bfs+正难则反
步骤一：
定义一个相同大小的dis矩阵，每一个位置都填入-1；
步骤二：
遍历整个原始矩阵，每一个0点的位置相对应到dis矩阵，并每一个点都填入为0，并将每一个零点都添加到队列
步骤三：
对于队列中的每一个元素都进行bfs查找，没进行依次查找，dis相对应的位置都加一，直到遍历完所有队列中的元素或者遍历到的所有元素都在边界为止；
使用dis【】【】矩阵的好处：
1、dist[i][j] = -1 表示当前位置没有被扫描标记
2、dist[i][j] != -1,表示当前位置里面存在的是当前位置到0的最短距离至此，代码如下：
class Solution { int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; public int[][] updateMatrix(int[][] mat) { int m = mat.length,n = mat[0].length; //dist[i][j] = -1 表示当前位置没有被扫描标记 //dist[i][j] != -1,表示当前位置里面存在的是当前位置到0的最短距离 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(mat[i][j] == 0){ dist[i][j] = 0; q.add(new int[]{i,j}); } } } //2、一层一层的往外扩 while(!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 && y >=0 && y<n && x<m && dist[x][y] == -1){ dist[x][y] = dist[a][b]+1; q.add(new int[]{x,y}); } } } return dist; } }
第二题
1020. 飞地的数量
解法：正难则反+多源bfs
从矩阵的边界1开始开始进行bfs遍历，对于每一个被遍历到的1进行标记；等边界的所有1bfs遍历完之后，没有被标记的1的个数就是我们所要求解的值；
至此，代码如下：
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、多源bfs while(!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 && y >=0 && y<n && x<m && !vis[x][y] && grid[x][y] ==1 ){ vis[x][y] = true; q.add(new int[]{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; } }
第三题
1765. 地图中的最高点
解法：正难则反+多源bfs
原矩阵如下：
新定义一个数组，着所有的数值为-1，然后遍历原始矩阵，其1点位置赋值为0；如下：
将每一个0点放入到队列中，并按照出队的顺序对每一个元素进行上下左右的遍历；每一个被遍历的位置都是在最初的位置的值加一，这样一直到遍历完所有的当前非0点，得到新的矩阵；
第一次bfs遍历：
第二次bfs遍历：
至此，代码如下：
class Solution { int[] dx = {0,0,-1,1}; int[] dy = {1,-1,0,0}; public int[][] highestPeak(int[][] Water) { int m = Water.length,n = Water[0].length; int[][] WaterModel = new int[m][n]; for(int i = 0 ;i< m; i++){ for(int j = 0 ; j< n ;j++){ WaterModel[i][j] = -1; } } Queue<int[]> q = new LinkedList<>(); //1、处理所有的水域 for(int i = 0 ;i< m; i++){ for(int j = 0 ; j< n ;j++){ if(Water[i][j] == 1){ q.add(new int[]{i,j}); WaterModel[i][j] = 0; } } } //2\多源bfs while(!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 && WaterModel[x][y] == -1){ q.add(new int[]{x,y}); WaterModel[x][y] = WaterModel[a][b] + 1; } } } return WaterModel; } }
第四题
1162. 地图分析
解法：正难则反+多源bfs
本题询问的0到1的最长距离，我们可以转换思路，求解每一个1到0的最长距离；
原始矩阵如下：
定义模拟矩阵，首先都赋值为-1；之前原始矩阵为1的地方赋值为0，并开始根据这些0激进型bfs遍历；
至此，代码如下：
class Solution { int[] dx = {0,0,-1,1}; int[] dy = {1,-1,0,0}; public int maxDistance(int[][] grid) { int m = grid.length,n = grid[0].length; int[][] model = new int[m][n]; for(int i = 0 ;i< m; i++){ for(int j = 0 ; j< n ;j++){ model[i][j] = -1; } } Queue<int[]> q = new LinkedList<>(); for(int i = 0 ;i< m; i++){ for(int j = 0 ; j< n ;j++){ if(grid[i][j] == 1){ q.add(new int[]{i,j}); model[i][j] = 0; } } } int ret = -1; while(!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 && model[x][y] == -1){ q.add(new int[]{x,y}); model[x][y] = model[a][b] + 1; ret = Math.max(ret,model[x][y]); } } } return ret; } }
ps：本次的内容就到这里了，如果对你有所帮助的话，就请一键三连哦!!!
