当前位置: 首页 > news >正文

代码随想录-算法训练营-番外(图论02:岛屿数量,岛屿的最大面积)

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

http://www.lryc.cn/news/502855.html

相关文章:

  • 20 go语言(golang) - gin框架安装及使用(一)
  • 重生之我在学Vue--第3天 Vue 3 模板语法与指令
  • 电脑win11家庭版升级专业版和企业版相关事项
  • docker 架构详解
  • tinyCam Pro 用于远程监控,控制和录制您的私人公共网络或IP摄像机
  • Flask 验证码自动生成
  • vmpwn小总结
  • 开源密码管理器 Bitwarden 一站式管理所有密码以及 2FA
  • 标准体重计算API集成指南
  • 多个终端查看的history不一样,如何确保多个终端会话之间的 history 一致,减少历史记录差异
  • Spring Boot整合EasyExcel并行导出及Zip压缩下载
  • Docker 对 iptables 规则的自动配置,这句话是什么意思
  • 使用aarch64-unknown-linux-musl编译生成静态ARM64可执行文件
  • 【SpringBoot中出现循环依赖错误】
  • 数据仓库-基于角色的权限管理(RBAC)
  • springboot3整合javafx解决bean注入问题
  • .NET 8 Blazor Web项目中的 .razor 文件与 .cshtml 文件的本质区别
  • SpringBoot快速使用
  • 【C语言实现:用队列模拟栈与用栈模拟队列(LeetCode 225 232)】
  • 远程控制软件对比与使用推荐
  • vue canvas 绘制选定区域 矩形框
  • 【SpringCloud】OpenFeign配置时间Decode
  • Xerces-C,一个成熟的 C++ XML 解析库!
  • 6.2 MapReduce工作原理
  • 一次旧业务系统迁移收缩的经历
  • MVC配置文件及位置
  • 如何解决samba服务器共享文件夹不能粘贴文件
  • 【中工开发者】鸿蒙商城app
  • (九)机器学习 - 多项式回归
  • Qt编写区位码gb2312、机内码、国标码————附带详细介绍和编码实现