室内设计装修网站,wordpress页面标题字号,广告制作合同模板免费,常用网店系统前言#xff1a;前段时间论文开题落下了很多进度#xff0c;今天开始会尽快赶上
99.岛屿数量 深搜
思路#xff1a;对地图进行遍历遇到一个没有遍历过的陆地节点#xff0c;计数器就1#xff0c;并把该节点所能遍历到的陆地都标记上#xff1b;遇到标记过的陆地节点和海…前言前段时间论文开题落下了很多进度今天开始会尽快赶上
99.岛屿数量 深搜
思路对地图进行遍历遇到一个没有遍历过的陆地节点计数器就1并把该节点所能遍历到的陆地都标记上遇到标记过的陆地节点和海洋节点的时候直接跳过。
代码如下
import java.util.Scanner;
public class Main{//定义前进的方向public static int[][] dir{{0,1},{1,0},{-1,0},{0,-1}};//深度搜索函数public static void dfs(boolean[][] visited,int[][] grid,int x,int y){for(int i0;i4;i){int nextXxdir[i][0];int nextYydir[i][1];if(nextX0 || nextY0 || nextXgrid.length || nextYgrid[0].length) continue;if(!visited[nextX][nextY] grid[nextX][nextY]1){visited[nextX][nextY]true;dfs(visited,grid,nextX,nextY);}}}public static void main (String[] args) {//构建地图Scanner scan new Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][] gridnew int[n][m];for(int i0;in;i){for(int j0;jm;j){grid[i][j]scan.nextInt();}}//判断是否为岛屿int result0;boolean[][] visitednew boolean[n][m];for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j] grid[i][j]1){result;visited[i][j]true;dfs(visited,grid,i,j);}}}System.out.println(result);}
}99.岛屿数量 广搜
注意要在节点加入队列时就标记走过如果从队列拿出来的时候再标记走过就会导致很多节点重复加入队列。
广度搜索使用队列存放下一层搜索的节点与DFS的区别是不需要调用自身把队列中的元素遍历完即可。
代码如下
import java.util.*;
class Pair{int x;int y;public Pair(int x, int y) {this.x x;this.y y;}
}public class Main{//定义前进的方向public static int[][] dir{{0,1},{1,0},{-1,0},{0,-1}};public static void bfs(boolean[][] visited,int[][] grid,int x,int y){QueuePair queuenew LinkedList();queue.add(new Pair(x,y));visited[x][y]true;while(!queue.isEmpty()){Pair curqueue.poll();int curXcur.x;int curYcur.y;for(int i0;i4;i){int nextXcurXdir[i][0];int nextYcurYdir[i][1];if(nextX0 || nextY0 || nextXgrid.length || nextYgrid[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 scan new Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][] gridnew int[n][m];for(int i0;in;i){for(int j0;jm;j){grid[i][j]scan.nextInt();}}int result0;boolean[][] visitednew boolean[n][m];for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j] grid[i][j]1){result;bfs(visited,grid,i,j);}}}System.out.println(result);}
}100.岛屿的最大面积
思路只需要在标记一个陆地节点周边所有陆地节点时对这个岛屿的面积计数即可最后比较获得最大的面积。使用全局静态变量count来计数。
dfs只处理下一个节点即在主函数遇到岛屿就计数为1dfs处理接下来的相邻陆地.
代码如下
import java.util.Scanner;
public class Main{//定义前进的方向public static int[][] dir{{0,1},{1,0},{-1,0},{0,-1}};public static int count;//深度搜索函数public static void dfs(boolean[][] visited,int[][] grid,int x,int y){for(int i0;i4;i){int nextXxdir[i][0];int nextYydir[i][1];if(nextX0 || nextY0 || nextXgrid.length || nextYgrid[0].length) continue;if(!visited[nextX][nextY] grid[nextX][nextY]1){visited[nextX][nextY]true;count;dfs(visited,grid,nextX,nextY);}}}public static void main (String[] args) {//构建地图Scanner scan new Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][] gridnew int[n][m];for(int i0;in;i){for(int j0;jm;j){grid[i][j]scan.nextInt();}}//判断是否为岛屿boolean[][] visitednew boolean[n][m];int result0;for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j] grid[i][j]1){count1;visited[i][j]true;dfs(visited,grid,i,j);}if(countresult) resultcount;}}System.out.println(result);}
}
