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博客
