算法打卡：第十一章图论part04

今日收获：字符串接龙，有向图的完全可达性，岛屿的周长

1. 字符串接龙

题目链接：110. 字符串接龙 (kamacoder.com)

思路：广度优先遍历适合解决两个点之间的最短路径问题，通常使用队列模拟一圈圈遍历。

（1）对于起始字符串的每一个字符分别替换为a到z的字符，如果新字符在字典中，就将其加入队列，作为本圈可以遍历到的字符串。然后再将原来的字符还原，接着替换下一个字符

（2）需要利用visited集合判断变化后的新字符串是否访问过，否则可能会出现重复变化的情况。

（3）每一层队列遍历完成后，路径数加1；如果变化字符后出现了结果字符串，直接返回

方法：

java">import java.util.Scanner;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;public class Main{public static void main(String[] args){// 接收数据Scanner sc=new Scanner(System.in);int N=sc.nextInt();sc.nextLine(); // 消耗换行符String[] strs=sc.nextLine().split(" ");HashSet<String> strList=new HashSet<>();  // 便于查找字典for (int i=0;i<N;i++){strList.add(sc.nextLine());}int result=bfs(strs[0],strs[1],strList);System.out.println(result);}public static int bfs(String beginStr,String endStr,HashSet<String> strList){// 存放广度优先遍历的元素Queue<String> queue=new LinkedList<>();// 防止元素重复访问HashSet<String> visited=new HashSet<>();queue.offer(beginStr);visited.add(beginStr);int path=1;  // 起点算一次while (!queue.isEmpty()){int size=queue.size();  // 当前层的元素数量for (int k=0;k<size;k++){String current=queue.poll();// 变换当前字符串中的每一个字符，广度优先遍历char[] chars=current.toCharArray();int len=chars.length;for (int i=0;i<len;i++){char origin=chars[i];for (char c='a';c<='z';c++){chars[i]=c;String newStr=new String(chars);if(newStr.equals(endStr)){  // 遇到结果直接返回return path+1;}if (!visited.contains(newStr)&&strList.contains(newStr)){  // 如果变换后的字符串存在于字典中queue.offer(newStr);visited.add(newStr);}}chars[i]=origin;}}path++; // 遍历完一层}return 0; // 不存在转换序列}
}

总结：nextInt不会消耗换行符，接下来用nextLine可以消耗换行符，否则下一个nextLine读到的是空字符串。

2. 有向图的完全可达性

题目链接：105. 有向图的完全可达性 (kamacoder.com)

思路：利用深度优先遍历对节点进行染色。

（1）利用邻接表存储图，遍历当前节点的相邻节点时可以利用增强for循环

（2）递归函数中处理的是当前节点。如果已经访问过则返回，否则标记当前节点已访问并且深度优先遍历其相邻节点

（3）遍历访问数组判断其他节点是否都能访问到

方法：

java">import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int K=sc.nextInt();// 邻接表List<List<Integer>> grid=new ArrayList<>(N+1);for (int i=0;i<N+1;i++){grid.add(new LinkedList<>());}for (int i=0;i<K;i++){int s=sc.nextInt();int t=sc.nextInt();grid.get(s).add(t);}boolean[] visited=new boolean[N+1];dfs(grid,1,visited);// 判断所有节点是否能到达for (int i=2;i<N+1;i++){if (!visited[i]){System.out.println(-1);return;}}System.out.println(1);}public static void dfs(List<List<Integer>> grid,int curr,boolean[] visited){// 处理当前节点if (visited[curr]){  // 当前节点被访问过return;}visited[curr]=true;  // 标记当前节点for (int next:grid.get(curr)){dfs(grid,next,visited);}}
}

3. 岛屿的周长

题目链接：106. 岛屿的周长 (kamacoder.com)

思路：遇到陆地就判断其周围的格子是否出界或者是水域，是的话就算岛屿的一条边。不涉及深搜或广搜。

方法：

java">import java.util.Scanner;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}int result=0;for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (grid[i][j]==1){  // 计算陆地周围是否为水域或出界for (int k=0;k<4;k++){int nextX=i+around[k][0];int nextY=j+around[k][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){result++;continue;}if (grid[nextX][nextY]==0){result++;}}}}}System.out.println(result);}
}