99. 島嶼數量
時間限制：1.000S??空間限制：256MB
題目描述
給定一個由?1（陸地）和 0（水）組成的矩陣，你需要計算島嶼的數量。島嶼由水平方向或垂直方向上相鄰的陸地連接而成，并且四周都是水域。你可以假設矩陣外均被水包圍。
輸入描述
第一行包含兩個整數 N, M，表示矩陣的行數和列數。
后續 N 行，每行包含 M 個數字，數字為 1 或者 0。
輸出描述
輸出一個整數，表示島嶼的數量。如果不存在島嶼，則輸出 0。
輸入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1輸出示例
3提示信息
根據測試案例中所展示，島嶼數量共有 3 個，所以輸出 3。
數據范圍：
1 <= N, M <= 50
思路:
注意題目中每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
也就是說斜角度鏈接是不算了
本題思路，是用遇到一個沒有遍歷過的節點陸地，計數器就加一，然后把該節點陸地所能遍歷到的陸地都標記上。
在遇到標記過的陸地節點和海洋節點的時候直接跳過。 這樣計數器就是最終島嶼的數量。
dfs:
import java.util.*;class Main{public static void main(String[] args){int n,m;Scanner scanner = new Scanner(System.in);n=scanner.nextInt();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();}}int result=0;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){result++;visited[i][j]=true;dfs(visited,map,i,j);}}}System.out.println(result);}public static void dfs(boolean[][] visited,int[][] map,int x,int y){int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};for(int i=0;i<4;i++){int newx=x+dir[i][0];int newy=y+dir[i][1];if(newx>=0&&newx<map.length&&newy>=0&&newy<map[x].length&&!visited[newx][newy]&&map[newx][newy]==1){visited[newx][newy]=true;dfs(visited,map,newx,newy);}}}
}BFS:
注意這里為了避免超時,加入隊列就標記為訪問過,避免結點的重復加入
import java.util.*;class Main{public static void main(String[] args){int n,m;Scanner scanner = new Scanner(System.in);n=scanner.nextInt();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();}}int result=0;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){result++;visited[i][j]=true;bfs(visited,map,i,j);}}}System.out.println(result);}public static void bfs(boolean[][] visited, int[][] map, int x, int y) {int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};Queue<int[]> queue = new LinkedList();queue.offer(new int[]{x, y});visited[x][y] = true;while (!queue.isEmpty()) {int[] poll = queue.poll();int curx = poll[0];int cury = poll[1];for (int i=0;i<4;i++){int newx=curx+dir[i][0];int newy=cury+dir[i][1];if(newx>=0&&newx<map.length&&newy>=0&&newy<map[x].length&&!visited[newx][newy]&&map[newx][newy]==1){queue.add(new int[]{newx,newy});visited[newx][newy]=true;}}}}
}100. 島嶼的最大面積
時間限制：1.000S??空間限制：256MB
題目描述
給定一個由?1（陸地）和 0（水）組成的矩陣，計算島嶼的最大面積。島嶼面積的計算方式為組成島嶼的陸地的總數。島嶼由水平方向或垂直方向上相鄰的陸地連接而成，并且四周都是水域。你可以假設矩陣外均被水包圍。
輸入描述
第一行包含兩個整數 N, M，表示矩陣的行數和列數。后續 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。
輸出描述
輸出一個整數，表示島嶼的最大面積。如果不存在島嶼，則輸出 0。
輸入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1輸出示例
4提示信息
樣例輸入中，島嶼的最大面積為 4。
數據范圍：
1 <= M, N <= 50。
思路:本題與上題一樣,就是多了求每個島嶼面積的步驟
import java.util.*;class Main {public static void main(String[] args) {int n, m;Scanner scanner = new Scanner(System.in);n = scanner.nextInt();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();}}int result = 0;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) {visited[i][j] = true;int s= dfs(visited, map, i, j);result=Math.max(result,s);}}}System.out.println(result);}public static int dfs(boolean[][] visited, int[][] map, int x, int y) {int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};int s=0;Queue<int[]> queue = new LinkedList();queue.offer(new int[]{x, y});s++;visited[x][y] = true;while (!queue.isEmpty()) {int[] poll = queue.poll();int curx = poll[0];int cury = poll[1];for (int i=0;i<4;i++){int newx=curx+dir[i][0];int newy=cury+dir[i][1];if(newx>=0&&newx<map.length&&newy>=0&&newy<map[x].length&&!visited[newx][newy]&&map[newx][newy]==1){queue.add(new int[]{newx,newy});s++;visited[newx][newy]=true;}}}
return s;}
}
方法)
