代码随想录训练营第五十一天| 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;//一定要先标记当前节点为true

        while(!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);
    }
}

打卡冲冲冲