代码随想录第51天

99.岛屿数量 深搜

import java.util.*;class Main{static int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};static boolean[][] visited;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grids = new int[n][m];for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {grids[i][j] = sc.nextInt();}}int cnt = 0;visited = new boolean[n][m];for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(grids[i][j] == 1 && !visited[i][j]) {cnt++;dfs(grids, i, j);}}}System.out.println(cnt);}private static void dfs(int[][] grids, int x, int y) {visited[x][y] = true;for(int i = 0; i < 4; i++) {int nextX = x + directions[i][0];int nextY = y + directions[i][1];if(check(grids, nextX, nextY)) {dfs(grids, nextX, nextY);}}}private static boolean check(int[][] grids, int x, int y) {int n = grids.length;int m = grids[0].length;return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y] && grids[x][y] == 1;}
}

99.岛屿数量 广搜

import java.util.*;// dfs
class Main {public static void main (String[] args) {Main main = new Main();Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] island = new int[n][m];for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {island[i][j] = sc.nextInt();}}int result = main.getIslandNum(island);System.out.println(result);}public int getIslandNum(int[][] island) {int numsIsland = 0;int row = island.length;int col = island[0].length;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (island[i][j] == 1) {++numsIsland;dfs(island, i, j);}}}return numsIsland;}public void dfs(int[][] island, int x, int y) {int row = island.length;int col = island[0].length;if (x < 0 || y < 0 || x >= row || y >= col || island[x][y] == 0) {return;}island[x][y] = 0; // 标记为已经访问dfs(island, x, y + 1);dfs(island, x, y - 1);dfs(island, x + 1, y);dfs(island, x - 1, y);}
}

100.岛屿的最大面积

#include <stdio.h>
#include <stdlib.h>// 四方向向量 下 右 上 左（逆时针）
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};int bfs(int **G, int N, int M, int x, int y);int main(void) {int N, M;scanf("%d %d", &N, &M);// 创建N行M列矩阵int **G = (int **)calloc(N, sizeof(int *));for(int i = 0; i < N; ++ i) {G[i] = (int *)calloc(M, sizeof(int));for(int j = 0; j < M; ++ j) {scanf("%d", &G[i][j]);}}// DFS函数int max = 0;int curMax;for(int i = 0; i < N; ++ i) {for(int j = 0; j < M; ++ j) {if (G[i][j]) {G[i][j] = 0;curMax = bfs(G, N, M, i, j);max = max < curMax ? curMax : max;}}}printf("%d\n", max);// 释放内存for(int i = 0; i < N; ++ i) free(G[i]);free(G);return 0;
}int bfs(int **G, int N, int M, int x, int y) {int queue[500][2];int front = 0, rear = 0;queue[rear][0] = x;queue[rear ++][1] = y;int curx, cury;int res = 1;while(front < rear) {curx = queue[front][0];cury = queue[front ++][1];for(int i = 0; i < 4; ++ i) {int nextx = curx + dx[i];int nexty = cury + dy[i];if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < M) {if (G[nextx][nexty]) {G[nextx][nexty] = 0;++ res;queue[rear][0] = nextx;queue[rear ++][1] = nexty;}}}}return res;
}