字符串接龙

java">import java.util.*;public class Test {public static int bfs(String beginStr,String endStr,List<String> wordList){HashSet<String> set=new HashSet<>(wordList);Queue<String> que=new LinkedList<>();HashMap<String,Integer> visit=new HashMap<>();que.offer(beginStr);visit.put(beginStr, 1);while (!que.isEmpty()) {String curWord=que.poll();int path=visit.get(curWord);for(int i=0;i<curWord.length();i++){char[]ch=curWord.toCharArray();for(char k='a';k<='z';k++){ch[i]=k;String newWord=new String(ch);if(newWord.equals(endStr))return path+1;if(set.contains(newWord)&&!visit.containsKey(newWord)){visit.put(newWord, path+1);que.offer(newWord);}}}}return 0;}public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();in.nextLine();String s=in.nextLine();String[]str=s.split(" ");String beginStr=str[0];String endStr=str[1];List<String> wordList=new ArrayList<>();for(int i=0;i<n;i++){wordList.add(in.nextLine());}int res=bfs(beginStr, endStr, wordList);System.out.println(res);}
}

有向图的完全可达性

java">import java.util.*;public class Test {public static void dfs(List<List<Integer>> adjList,int node,boolean[]visit){if(visit[node])return;visit[node]=true;List<Integer> list=adjList.get(node);for(int key:list){dfs(adjList,key,visit);}}public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();List<List<Integer>> adjList=new ArrayList<>();boolean[]visit=new boolean[n+1];for(int i=0;i<=n;i++){adjList.add(new ArrayList<>());}for(int i=0;i<m;i++){int u=in.nextInt();int v=in.nextInt();adjList.get(u).add(v);adjList.get(v).add(u);}dfs(adjList,1,visit);for(int i=1;i<=n;i++){if(!visit[i]){System.out.println(-1);return;}}System.out.println(1);}
}

岛屿的周长

注意只有一个岛屿且岛屿中间没有水域
因此可以计算每个区域四周的情况来算周长。