算法day31

第一题

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、多源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 && 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\多源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 && 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;}
}