阅读量:1
代码随想三刷图论篇2
104. 建造最大岛屿
题目
代码
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]; used = new boolean[N][M]; for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ pic[i][j] = sc.nextInt(); if(pic[i][j]==0){ used[i][j] = true; } } } int maxCount = 0; int index = 1; Map<Integer,Integer> map = new HashMap(); for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==1){ list.clear(); dfs(pic,i,j); for(int k = 0;k<list.size();k++){ int[] temp= list.get(k); pic[temp[0]][temp[1]] = index; } map.put(index,list.size()); maxCount = Math.max(maxCount,list.size()); index++; } } } for(int i =0;i<N;i++){ for(int j =0;j<M;j++){ if(pic[i][j]==0){ Set<Integer> sett = new HashSet(); int count = 1; if(i>=1 && !sett.contains(pic[i-1][j])){ count+=map.getOrDefault(pic[i-1][j],0); sett.add(pic[i-1][j]); } if(j>=1 && !sett.contains(pic[i][j-1])){ count+=map.getOrDefault(pic[i][j-1],0); sett.add(pic[i][j-1]); } if(i<pic.length-1 && !sett.contains(pic[i+1][j])){ count += map.getOrDefault(pic[i+1][j],0); sett.add(pic[i+1][j]); } if(j<pic[0].length-1 && !sett.contains(pic[i][j+1])){ count+=map.getOrDefault(pic[i][j+1],0); sett.add(pic[i][j+1]); } maxCount = Math.max(maxCount,count); } } } System.out.println(maxCount); } static boolean[][] used; static List<int[]> list = new ArrayList(); public static void dfs(int[][] pic,int i,int j){ if(i<0||j<0||i>=pic.length||j>=pic[0].length||used[i][j]){ return; } used[i][j] = true; list.add(new int[]{i,j}); if(i>=1){ dfs(pic,i-1,j); } if(j>=1){ dfs(pic,i,j-1); } if(i<pic.length-1){ dfs(pic,i+1,j); } if(j<pic[0].length-1){ dfs(pic,i,j+1); } } } 110. 字符串接龙
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = Integer.valueOf(sc.nextLine()); String beginStr = sc.next(); String endStr = sc.next(); Set<String> strList = new HashSet(); for(int i = 0;i<N;i++){ strList.add(sc.next()); } int count = 0; Deque<String> queue = new LinkedList(); queue.addLast(beginStr); while(!queue.isEmpty()){ count++; int size = queue.size(); for(int step = 0;step<size;step++){ String word = queue.removeFirst(); for(int i=0;i< word.length();i++){ char[] chars = word.toCharArray(); for(char k = 'a';k<='z';k++){ chars[i] = k; String newWord = String.valueOf(chars); if(newWord.equals(endStr)){ System.out.println(count+1); return; } if(strList.contains(newWord)){ strList.remove(newWord); queue.addLast(newWord); } } } } } System.out.println(0); } } 105. 有向图的完全可达性
题目
代码
import java.util.*; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); Map<Integer,Set<Integer>> map = new HashMap(); for(int i =1;i<=N;i++){ map.put(i,new HashSet()); } for(int i = 0;i<K;i++){ int num1 = sc.nextInt(); int num2 = sc.nextInt(); map.get(num1).add(num2); } used = new boolean[N+1]; dfs(map,1); for(int i =1;i<=N;i++){ if(!used[i]){ System.out.println(-1); return; } } System.out.println(1); } static boolean[] used; public static void dfs(Map<Integer,Set<Integer>> map,int key){ if(used[key]){ return; } used[key] = true; Set<Integer> set =map.get(key); for(int nextNum:set){ dfs(map,nextNum); } } } 106. 岛屿的周长
题目
代码
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 sum = 0; // 陆地数量 int cover = 0; // 相邻数量 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (pic[i][j] == 1) { sum++; // 统计总的陆地数量 // 统计上边相邻陆地 if(i - 1 >= 0 && pic[i - 1][j] == 1) cover++; // 统计左边相邻陆地 if(j - 1 >= 0 && pic[i][j - 1] == 1) cover++; // 为什么没统计下边和右边？ 因为避免重复计算 } } } System.out.println(sum * 4 - cover * 2 ); } } 