代码随想录算法训练营第五六天| 99. 岛屿数量 100. 岛屿的最大面积

今日任务

99. 岛屿数量 深度搜搜
99. 岛屿数量 广度搜索
100. 岛屿的最大面积

99. 岛屿数量

题目链接： 99. 岛屿数量

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 (nextX < 0 || nextY < 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 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 res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {res++;visited[i][j] = true;dfs(visited, i, j, grid);}}}System.out.println(res);}}

99. 岛屿数量

题目链接： 99. 岛屿数量

import java.util.Scanner;
import java.util.*;public class Main {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<int[]>  queue = new LinkedList<>();queue.add(new int[]{x, y});visited[x][y] = true;while (!queue.isEmpty()) {int curX = queue.peek()[0];int curY = queue.peek()[1];queue.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) {queue.add(new int[]{nextX, nextY});visited[nextX][nextY] = true;}}}}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();}}int res = 0;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {res++;bfs(visited, i, j, grid);}}}System.out.println(res);}}

100. 岛屿的最大面积

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

import java.util.*;
public class Main {public static int[][] dir = {{0, 1},{1, 0},{-1, 0},{0, -1}};public static int res = 0;public static void bfs(boolean[][] visited, int x, int y, int[][] grid){Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{x, y});visited[x][y] = true;while (!queue.isEmpty()) {int curX = queue.peek()[0];int curY = queue.peek()[1];queue.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) {res++;queue.add(new int[]{nextX, nextY});visited[nextX][nextY] = true;}}}}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();}}int max = 0;boolean[][] visited = new boolean[grid.length][grid[0].length];for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (!visited[i][j] && grid[i][j] == 1) {res = 1;visited[i][j] = true;bfs(visited, i, j, grid);}max = Math.max(max, res);}}System.out.println(max);}    }