阅读量:1
代码随想三刷图论篇1
98. 所有可达路径
题目
代码
import java.util.*; class Main{ public static void main(String [] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt();//节点 int M = sc.nextInt();//边数 int[][] pic = new int[N+1][N+1];//0不用 for(int i =0;i<M;i++){ pic[sc.nextInt()][sc.nextInt()] = 1; } used = new boolean[N+1]; for(int i = 1;i<=1;i++){ paths.add(i); dfs(pic,i,N); paths.remove(paths.size()-1); } for(int i =0;i<result.size();i++){ for(int j =0;j<result.get(i).size();j++){ System.out.print(result.get(i).get(j)); if(j<result.get(i).size()-1){ System.out.print(" "); } } System.out.println(); } if(result.size()<=0){ System.out.println(-1); } } static List<List<Integer>> result = new ArrayList(); static List<Integer> paths = new ArrayList(); static boolean[] used; public static void dfs(int[][] pic,int node,int N){ if(paths.get(paths.size()-1)==N){ result.add(0,new ArrayList(paths)); return; } for(int j =1;j<pic[0].length;j++){ if(!used[j]&&pic[node][j]==1){ used[j] = true; paths.add(j); dfs(pic,j,N); paths.remove(paths.size()-1); used[j] = false; } } } } 99. 岛屿数量
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] pic = new int[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); } } for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==1){ count++; dfs(pic,i,j); } } } System.out.println(count); } static int count = 0; public static void dfs(int[][] pic,int i,int j){ pic[i][j] = 0; if(i>=1&&pic[i-1][j]==1){ dfs(pic,i-1,j); } if(j>=1&&pic[i][j-1]==1){ dfs(pic,i,j-1); } if(i<pic.length-1&&pic[i+1][j]==1){ dfs(pic,i+1,j); } if(j<pic[0].length-1&&pic[i][j+1]==1){ dfs(pic,i,j+1); } } } 100. 岛屿的最大面积
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] pic = new int[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); } } int maxCount = 0; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==1){ count=0; dfs(pic,i,j); maxCount = Math.max(maxCount,count); } } } System.out.println(maxCount); } static int count = 0; public static void dfs(int[][] pic,int i,int j){ pic[i][j] = 0; count++; if(i>=1&&pic[i-1][j]==1){ dfs(pic,i-1,j); } if(j>=1&&pic[i][j-1]==1){ dfs(pic,i,j-1); } if(i<pic.length-1&&pic[i+1][j]==1){ dfs(pic,i+1,j); } if(j<pic[0].length-1&&pic[i][j+1]==1){ dfs(pic,i,j+1); } } } 101. 孤岛的总面积
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] pic = new int[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); } } int maxCount = 0; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==1){ count=0; isL = true; dfs(pic,i,j); if(isL){ maxCount += count; } } } } System.out.println(maxCount); } static int count = 0; static boolean isL = true; public static void dfs(int[][] pic,int i,int j){ if(i==0||j==0||i==pic.length-1||j==pic[0].length-1){ isL = false; } pic[i][j] = 0; count++; if(i>=1&&pic[i-1][j]==1){ dfs(pic,i-1,j); } if(j>=1&&pic[i][j-1]==1){ dfs(pic,i,j-1); } if(i<pic.length-1&&pic[i+1][j]==1){ dfs(pic,i+1,j); } if(j<pic[0].length-1&&pic[i][j+1]==1){ dfs(pic,i,j+1); } } } 102. 沉没孤岛
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] pic = new int[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); } } for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==1){ count=0; isL = true; list.clear(); dfs(pic,i,j); if(!isL){ for(int k = 0;k<list.size();k++){ int [] temp = list.get(k); pic[temp[0]][temp[1]] = 1; } } } } } for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ System.out.print(pic[i][j]+" "); } System.out.println(); } } static int count = 0; static List<int[]> list = new ArrayList(); static boolean isL = true; public static void dfs(int[][] pic,int i,int j){ if(i==0||j==0||i==pic.length-1||j==pic[0].length-1){ isL = false; } list.add(new int[]{i,j}); pic[i][j] = 0; count++; if(i>=1&&pic[i-1][j]==1){ dfs(pic,i-1,j); } if(j>=1&&pic[i][j-1]==1){ dfs(pic,i,j-1); } if(i<pic.length-1&&pic[i+1][j]==1){ dfs(pic,i+1,j); } if(j<pic[0].length-1&&pic[i][j+1]==1){ dfs(pic,i,j+1); } } } 103. 水流问题
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] pic = new int[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); } } used1 = new boolean[N][M]; used2 = new boolean[N][M]; for(int j = 0;j<M;j++){ dfs(pic,0,j,false); dfs(pic,N-1,j,true); } for(int i = 0;i<N;i++){ dfs(pic,i,0,false); dfs(pic,i,M-1,true); } for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(used1[i][j]&&used2[i][j]){ System.out.println(i+" "+j); } } } } static boolean[][] used1; //是否访问过 static boolean[][] used2; //是否访问过 //暂存一回合可到达的坐标 static List<int[]> list = new ArrayList(); //是否到边 public static void dfs(int[][] pic,int i,int j,boolean flag){ if(flag){ if(used1[i][j]){ return; } used1[i][j] = true; }else{ if(used2[i][j]){ return; } used2[i][j] = true; } if(i>=1&&pic[i-1][j]>=pic[i][j]){ dfs(pic,i-1,j,flag); } if(j>=1&&pic[i][j-1]>=pic[i][j]){ dfs(pic,i,j-1,flag); } if(i<pic.length-1&&pic[i+1][j]>=pic[i][j]){ dfs(pic,i+1,j,flag); } if(j<pic[0].length-1&&pic[i][j+1]>=pic[i][j]){ dfs(pic,i,j+1,flag); } } } 