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

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

1. 字符串接龙

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

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

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

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

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

方法：

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）遍历访问数组判断其他节点是否都能访问到

方法：

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)

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

方法：

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);
    }
}