1. 卡码网 110. 字符串接龙
题目链接：https://kamacoder.com/problempage.php?pid=1183
文章链接：https://www.programmercarl.com/kamacoder/0110.字符串接龙.html
思路：
本题只需要求出最短路径的长度就可以了，不用找出具体路径。
所以这道题要解决两个问题：
- 图中的线是如何连在一起的
- 起点和终点的最短路径长度
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。
所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
另外需要有一个注意点： - 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
- 使用set来检查字符串是否出现在字符串集合里更快一些
import java.util.*;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(" ");List<String> wordList = new ArrayList<>();for (int i = 0; i < N; i++) {wordList.add(sc.nextLine());}// 打印结果int result = bfs(wordList,strs[0], strs[1]);System.out.println(result);}public static int bfs (List<String> wordList,String beginStr,String endStr) {Set<String> strSet = new HashSet<>(wordList);Map<String,Integer> resMap = new HashMap<>();Deque<String> deque = new ArrayDeque<>();deque.offer(beginStr);resMap.put(beginStr,1);while (!deque.isEmpty()) {String curWord = deque.poll();int path = resMap.get(curWord);// 对当前单词进行分析for (int i=0; i<curWord.length(); i++) {char[] wordArr = curWord.toCharArray();for (char k='a';k<='z';k++) {wordArr[i]=k;String temp = new String(wordArr);if (temp.equals(endStr)) {return path+1;}if (strSet.contains(temp) && !resMap.containsKey(temp)) {deque.offer(temp);resMap.put(temp,path+1);}//若resMap中存在temp，表示在此之前已经处理过该temp，要么同一层，要么更靠近核心，更短路径}}}return 0;}
}
卡码网 105.有向图的完全可达性
题目链接：https://kamacoder.com/problempage.php?pid=1177
文章链接：https://www.programmercarl.com/kamacoder/0105.有向图的完全可达性.html
思路：
本题有两种dfs的解法。
1.确认递归函数，参数
需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。
同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。
2.确认终止条件
遍历的时候，什么时候终止呢？
a.若处理当前访问的节点：即在for循环之前处理节点，此时需要终止条件
当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。
// 写法一：处理当前访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {if (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];for (int key : keys) {// 深度优先搜索遍历dfs(graph, key, visited);}
}
b.若处理下一个要访问的节点：即在for循环内处理新节点，此时不需要终止条件
处理目前搜索节点出发的路径的时候对 节点进行处理。这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。
// 写法二：处理下一个要访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {list<int> keys = graph[key];for (int key : keys) {if (visited[key] == false) { // 确认下一个是没访问过的节点visited[key] = true;dfs(graph, key, visited);}}
}
3.处理目前搜索节点出发的路径
本题是需要判断 1节点 是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。
时候需要回溯操作呢？
当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”， 如果不理解的话，去看我写的 0098.所有可达路径 的题解。
import java.util.*;public class Main {// static Map<Integer,List<Integer>> map = new HashMap<>();// public static void main (String[] args) {// Scanner sc = new Scanner(System.in);// int n=sc.nextInt();// int k=sc.nextInt();// int[] arr = new int[n+1];// for (int i=0;i<k;i++) {// int key=sc.nextInt();// int value=sc.nextInt();// List<Integer> list = map.getOrDefault(key,new ArrayList<>());// list.add(value);// map.put(key,list);// }// arr[1]=1;// dfs(map.get(1),arr);// for (int i=1;i<arr.length;i++) {// if (arr[i]==0) {// System.out.println(-1);// return;// }// }// System.out.println(1);// }// public static void dfs (List<Integer> list,int[] arr) {// if (list==null) {// return;// }// for (int i=0;i<list.size();i++) {//对当前可以到达的所有节点分别分析// int cur = list.get(i);// if (arr[cur] != 0) {// continue;// }// arr[cur] = 1;// dfs(map.get(cur),arr);// }// }public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();int k=sc.nextInt();List<List<Integer>> list = new ArrayList<>(n+1);for (int i=0;i<=n;i++) {list.add(new ArrayList<>());}for (int i=0;i<k;i++) {int key=sc.nextInt();int value=sc.nextInt();list.get(key).add(value);}boolean[] visted = new boolean[n+1];dfs(list,visted,1);for (int i=1;i<visted.length;i++) {if (visted[i]==false) {System.out.println(-1);return;}}System.out.println(1);}public static void dfs (List<List<Integer>> list,boolean[] visted,int key) {// 检查是否被访问过if (visted[key]) {return;}visted[key]=true;// 对当前可以到达的所有节点分别分析for (int i:list.get(key)) {dfs(list,visted,i);}}
}
卡码网 106.岛屿的周长
题目链接：https://kamacoder.com/problempage.php?pid=1178
文章链接：https://www.programmercarl.com/kamacoder/0106.岛屿的周长.html
思路：
遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。
1.如果该陆地上下左右的空格是有水域，则说明是一条边；
2.如果该陆地上下左右的空格出界了，则说明是一条边。
import java.util.*;public class Main {static int[][] dr = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};static int c=0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 行int m = sc.nextInt(); // 列int[][] matrix = new int[n][m];for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {matrix[i][j] = sc.nextInt();}}boolean[][] visted = new boolean[n][m];for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 检查是否是未被访问的陆地if (matrix[i][j]==1&&visted[i][j]==false) {dfs(matrix,visted,i,j);}}}System.out.println(c);}public static void dfs(int[][] matrix,boolean[][] visted,int x,int y) {// 检查是否是海洋或者已被访问if (matrix[x][y]==0||visted[x][y]) {return;}visted[x][y] = true;for (int i=0;i<4;i++) {int nextx = x+dr[i][0];int nexty = y+dr[i][1];// 检查是否越界if (nextx<0||nextx>=matrix.length||nexty<0||nexty>=matrix[0].length) {c++;continue;}if (matrix[nextx][nexty]==0) {c++;}dfs(matrix,visted,nextx,nexty);}}
}