day02 圖論part02
今日任務:島嶼數量,島嶼的最大面積
都是一個模子套出來的
https://programmercarl.com/kamacoder/0099.島嶼的數量深搜.html#思路往日任務:
day01 圖論part01 
今日任務:圖論理論基礎/所有可到達的路徑
代碼隨想錄圖論視頻部分還沒更新
https://programmercarl.com/kamacoder/圖論理論基礎.html#圖的基本概念

day02

島嶼數量

dfs

?import java.util.Scanner;?public class Main{public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};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 count = 0;for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){if( visited[i][j] == false && grid[i][j] == 1){count++;visited[i][j] = true;//訪問過了dfs(grid,i,j,visited);//一直找臨近陸地直到找不到}}}System.out.println(count);}private static void dfs(int[][] grid,int x,int y,boolean[][] visited){for(int i = 0; i < 4; i++){//x += dir[i][0];//這里錯了,x和y需要用四次,可是剛用一次值就改變了//y += dir[i][1];int x1 = x + dir[i][0];int y1 = y + dir[i][1];if(x1<0||y1<0||x1>= grid.length||y1>=grid[0].length)continue;//越界則繼續判斷下一個旁邊的位置if(!visited[x1][y1] && grid[x1][y1]==1)//旁邊是沒遇到過的陸地{visited[x1][y1]=true;dfs(grid,x1,y1,visited);//繼續找臨近陸地}}}}

bfs

main方法一樣,dfs和bfs有細微的差別,dfs是遇到陸地就遞歸直到越界,bfs是遇到陸地就加到queue里面直到queue為空

linkedlist實現queue,用到了isEmpty方法,peek方法和poll方法

?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) {Queue<pair> queue = new LinkedList<pair>();//定義坐標隊列，沒有現成的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);}// 定義 pair 類來表示坐標public static class pair {int first; // 橫坐標int second; // 縱坐標?// 構造函數public pair(int x, int y) {this.first = x;this.second = y;}}}

---

島嶼的最大面積

dfs

套島嶼數量的模板,變化很少(話說這道題怎么沒有答案啊)

?import java.util.Scanner;public class Main{public static int count;//這里變了public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};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 result = 0;//這里變了for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){if( visited[i][j] == false && grid[i][j] == 1){count = 1;visited[i][j] = true;dfs(grid,i,j,visited);result = Math.max(result, count);//這里變了}}}System.out.println(result);//這里變了}private static void dfs(int[][] grid,int x,int y,boolean[][] visited){for(int i = 0; i < 4; i++){int x1 = x + dir[i][0];int y1 = y + dir[i][1];if(x1<0||y1<0||x1>= grid.length||y1>=grid[0].length)continue;if(!visited[x1][y1] && grid[x1][y1]==1){visited[x1][y1]=true;count++;//這里變了dfs(grid,x1,y1,visited);}}}}

bfs

套模版,基本沒變化

?import java.util.*;?public class Main {public static int count;//多了這一行public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};?public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {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++) {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;count++;//多了這一行}}}}?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 result = 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) {count = 1;bfs(grid, visited, i, j);result = Math.max(result, count);//這里}}}System.out.println(result);}public static class pair {int first; int second;public pair(int x, int y) {this.first = x;this.second = y;}}}

---

感謝大佬分享:

代碼隨想錄算法訓練營第五十一天|Day51 圖論-CSDN博客