孤岛问题算法题
2021-01-09 17:31
标签：vat div java spl amp port 方法 char color 我们用一个二维数组表示这个地图，地图中的 1 表示陆地，0 表示水域。一个岛屿是指由上下左右相连的陆地，并且被水域包围的区域。 孤岛问题算法题 标签：vat div java spl amp port 方法 char color 原文地址：https://www.cnblogs.com/seedss/p/12958299.html问题：在一个地图中，找出一共有多少个岛屿。
你可以假设地图的四周都是水域。 1 package com.guava;
2
3 import java.util.Scanner;
4
5 public class Main2 {
6
7 private int m = 0, n = 0;
8
9 int res = 0;
10
11 public static void main(String[] args) {
12 Scanner sc = new Scanner(System.in);
13 String[] in = sc.nextLine().split(" ");
14 int m = Integer.parseInt(in[0]);
15 int n = Integer.parseInt(in[1]);
16 int i = 0;
17 int[][] grid = new int[m][n];
18 while (i m) {
19 if (sc.hasNext()) {
20 String[] arr = sc.nextLine().split(" ");
21 int j = 0;
22 while (j n) {
23 grid[i][j] = Integer.parseInt(arr[j]);
24 j++;
25 }
26 }
27 i++;
28 }
29
30 Main2 main = new Main2();
31 System.out.println(main.getNumIslands(grid));
32
33 }
34
35 //方法一：会改变输入的二维数组
36 public int getNumIslands(int[][] grid) {
37 m = grid.length;
38 n = grid[0].length;
39 if (m == 0) {
40 return 0;
41 }
42
43 if (n == 0) {
44 return 0;
45 }
46
47 for (int i = 0; i ) {
48 for (int j = 0; j ) {
49 if (grid[i][j] != 1) continue;
50 res++;
51 //回溯法
52 calculateIsland(grid, i, j);
53 }
54 }
55 return res;
56 }
57
58 public void calculateIsland(int[][] grid, int i, int j) {
59 if (i 0 || i >= m || j 0 || j >= n) {
60 return;
61 }
62 if (grid[i][j] == 1) {
63 grid[i][j] = 0;
64 calculateIsland(grid, i - 1, j);
65 calculateIsland(grid, i + 1, j);
66 calculateIsland(grid, i, j - 1);
67 calculateIsland(grid, i, j + 1);
68 }
69 }
70
71
72 //方法二：使用与输入的二位数组相同大小的二维数组visit，来保存是否被遍历到。
73 public int getLands(char[][] lands) {
74 if (lands.length == 0) {
75 return 0;
76 }
77 int count = 0;
78 int row = lands.length;
79 int col = lands[0].length;
80 int[][] visit = new int[row][col];
81 for (int i = 0; i ) {
82 for (int j = 0; j ) {
83 if (visit[i][j] != 1 && lands[i][j] == ‘1‘) //注意此处的判断条件
84 count++;
85 //回溯法
86 BFS(lands, i, j, visit);
87 }
88 }
89
90 return count;
91 }
92
93 private void BFS(char[][] lands, int i, int j, int[][] visit) {
94 if (i 0 || i >= lands.length || j 0 || j >= lands[0].length) {
95 return;
96 }
97 if (lands[i][j] == ‘0‘) {
98 return;
99 }
100
101 if (lands[i][j] == ‘1‘) {
102 visit[i][j] = ‘0‘;
103 BFS(lands, i - 1, j, visit);
104 BFS(lands, i + 1, j, visit);
105 BFS(lands, i, j - 1, visit);
106 BFS(lands, i, j + 1, visit);
107 }
108 }
109 }
上一篇：PHP大文件分片上传/多线程上传