代码随想录训练营第五十一天| 99.岛屿数量 深搜 岛屿数量 广搜 100.岛屿的最大面积

99.岛屿数量 深搜

题目链接：99. 岛屿数量

讲解链接：代码随想录

就是dfs模版题目 在dfs里可以先定义方向数组移动 再遍历分别向四个方向移动 同时记得更新当前nextx nexty 再判断是否越界 再执行判断条件 当前位置未走过 visited[i][j] = false 一开始java赋值都是false 而且 当前位置是数字1 那就可以继续走 把当前位置设置为1 visited[i][j] = true 再在此基础上继续dfs递归得出结果 这里递归的回溯做法在判断边界条件的时候就已经做了 

在边界条件上懵了好久。。记住了

java：

import java.util.Scanner;public class Test99 {public static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};public static void dfs(boolean[][] visited, int x, int y,int [][] grid){for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nexty < 0 || nexty >= grid[0].length || nextx >= grid.length){continue;}if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty] = true;dfs(visited,nextx,nexty,grid);}}}public static void main(String[] args) {
//        for(int i = 0; i < dir.length; i++){
//            System.out.println(dir[i][0] + "/*******/" + dir[i][1]);
//        }Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int[][] grid = new int[m][n];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){grid[i][j] = scanner.nextInt();}}//录入地图boolean[][] visited = new boolean[m][n];int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!visited[i][j] && grid[i][j] == 1){ans++;visited[i][j] = true;dfs(visited,i,j,grid);}}}System.out.println(ans);}
}

岛屿数量 广搜  

题目链接：99. 岛屿数量

讲解链接：代码随想录

bfs做法最重要的就是要避免重复节点 避免重复节点 避免重复节点

错误做法：从队列中取出节点时才标记访问

java：

while (!queue.isEmpty()) {Node current = queue.poll();visited[current.x][current.y] = true; // 取出时才标记for (int[] direction : directions) {int nextX = current.x + direction[0];int nextY = current.y + direction[1];if (isValid(nextX, nextY, grid) && !visited[nextX][nextY]) {queue.offer(new Node(nextX, nextY)); // 可能重复加入}}
}

正确做法：在节点加入队列时标记访问

java：

while (!queue.isEmpty()) {Node current = queue.poll();for (int[] direction : directions) {int nextX = current.x + direction[0];int nextY = current.y + direction[1];if (isValid(nextX, nextY, grid) && !visited[nextX][nextY]) {visited[nextX][nextY] = true; // 加入队列时标记queue.offer(new Node(nextX, nextY));}}
}

 bfs写法 代码随想录里用了个pair 我不想用这个 用两个队列分别存x y的值作为两个队列当前出列的当前节点 具体看代码  也是OK的能过

java：

import java.util.*;
public class Test99 {public static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};public static void bfs(boolean[][] visited, int x,int y,int[][] grid){Queue<Integer> queue1 = new LinkedList<Integer>();Queue<Integer> queue2 = new LinkedList<Integer>();queue1.add(x);queue2.add(y);visited[x][y] = true;//一定要先标记当前节点为truewhile(!queue1.isEmpty()){int curx = queue1.poll();int cury = queue2.poll();//确定当前坐标for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.length || nexty >= grid[0].length){continue;}if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty] = true;queue1.add(nextx);queue2.add(nexty);}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int[][] grid = new int[m][n];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){grid[i][j] = scanner.nextInt();}}//录入地图boolean[][] visited = new boolean[m][n];int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!visited[i][j] && grid[i][j] == 1){ans++;bfs(visited,i,j,grid);}}}System.out.println(ans);}
}

100.岛屿的最大面积 

题目链接：100. 岛屿的最大面积

讲解链接：代码随想录

dfs做的比较方便 主要细节就是要求最大面积 遇到0或者遇到边界 遇到走过的1直接跳过 再用计数器求最大值

java:

import java.util.Scanner;class Test100 {static int count = 0;static int ans = 0;static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};public static void dfs(boolean[][] visited, int x,int y, int[][] grid){count++;visited[x][y]=true;for(int i = 0; i < 4;i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nexty < 0|| nextx >= grid.length|| nexty >= grid[0].length|| visited[nextx][nexty]|| grid[nextx][nexty] == 0){continue;}dfs(visited,nextx,nexty,grid);}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();boolean[][] visited = new boolean[m][n];int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = scanner.nextInt();}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!visited[i][j] && grid[i][j] == 1){count = 0;dfs(visited,i,j,grid);ans = Math.max(count,ans);}}}System.out.println(ans);}
}

打卡冲冲冲