目录

99. 计数孤岛

深搜版本

广搜版本

100. 最大岛屿的面积

---

学习链接：代码随想录

99. 计数孤岛

题目连接

        99. 计数孤岛

题目描述

        给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

       第一行包含两个整数 N, M，表示矩阵的行数和列数。

       后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

                输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

深搜版本

import java.util.Scanner;

public class Main {
    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(nextY<0||nextX<0||nextX>= grid.length||nextY>=grid[0].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) {
        Scanner sc = new Scanner(System.in);
        int m= sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j]=sc.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);
    }
}

广搜版本

将相邻的陆地都标记为已访问。一层一层遍历，发现新的陆地的时候result+1

在写代码过程中，只要加入队列则表示已经被访问过了，需要进行标记

import java.util.*;

public class Main {
    //下右上左逆时针遍历
    public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        //定义坐标队列，没有现成的pair类，在下面自定义了
        Queue<pair> queue = new LinkedList<pair>();
        queue.add(new pair(x, y));
        //遇到入队直接标记为优先，
        // 否则出队时才标记的话会导致重复访问，比如下方节点会在右下顺序的时候被第二次访问入队
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int curX = queue.peek().first;
            //当前横纵坐标
            int curY = queue.poll().second;
            for (int i = 0; i < 4; i++) {
                //顺时针遍历新节点next，下面记录坐标
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                    continue;
                }//去除越界部分
                if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                    queue.add(new pair(nextX, nextY));
                    //逻辑同上
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    ans++;
                    bfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(ans);
    }
}

100. 最大岛屿的面积

题目链接

        100. 最大岛屿的面积

题目描述

        给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

        第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

        输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

import java.util.*;
import java.math.*;

/**
 * DFS版
 */
public class Main{

    static final int[][] dir={{0,1},{1,0},{0,-1},{-1,0}};
    static int result=0;
    static int count=0;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j]=scanner.nextInt();
            }
        }
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(!visited[i][j]&&map[i][j]==1){
                    count=0;
                    dfs(map,visited,i,j);
                    result= Math.max(count, result);
                }
            }
        }
        System.out.println(result);
    }

    static void dfs(int[][] map,boolean[][] visited,int x,int y){
                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>=map.length||nextY>=map[0].length
                    ||visited[nextX][nextY]||map[nextX][nextY]==0)continue;
                    
                    dfs(map,visited,nextX,nextY);
                }
            }
}