算法训练营day54 | {110.字符串接龙, 105.有向图的完全可达性, 106.岛屿的周长}

第11章图论-part04，今天的应用题，在图的存储和连接上比岛屿问题难了。

110. 字符串接龙

• 题目链接：110.字符串接龙
• 文档讲解：代码随想录
• 视频讲解：图论：朴实无华的广搜这么难？ | 广度优先搜索 | 卡码网：110.字符串接龙
• 状态：求无权图两点之间的最短路径，用广搜更合适，只要搜到了终点，就一定是最短路径。

1.1 解题分析

从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4。

---

本题的难点有2个：

1. 节点之间怎么连接在一起？
   • 在搜索的过程中，我们可以枚举，用26个字母替换当前字符串的每一个字符，在看替换后 是否在 strList里出现过，就可以判断 两个字符串 是否是链接的。
2. 起点和终点的最短路径长度怎么算？
   • 在无权图中，求最短路，用深搜或者广搜就行，没必要用最短路算法。本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。

1.2 解题小结

▶

110.字符串接龙

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String beginStr = scanner.next();
        String endStr = scanner.next();
        scanner.nextLine();
        Set<String> wordSet = new HashSet<>();
        wordSet.add(beginStr);
        wordSet.add(endStr);
        while (n-- > 0) {
            wordSet.add(scanner.next());
        }
        
        bfs(beginStr, endStr, wordSet);

    }

    private static void bfs(String beginStr, String endStr, Set<String> wordSet) {
        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();
        queue.offerLast(beginStr);
        visited.add(beginStr);
        map.put(beginStr, 1);
        while (!queue.isEmpty()) {
            String curStr = queue.pollFirst();
            for (int i = 0; i < curStr.length(); i++) {
                StringBuilder cur = new StringBuilder(curStr);
                for (int j = 0; j < 26; j++) {
                    cur.setCharAt(i, (char)(j + 'a'));
                    String newWord = cur.toString();
                    if (newWord.equals(endStr)) {
                        System.out.println(map.get(curStr) + 1);
                        return;
                    }
                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        queue.offerLast(newWord);
                        visited.add(newWord);
                        map.put(newWord, map.get(curStr) + 1);
                    }
                }
            }
        }
        System.out.println(0);
    }
}

105. 有向图的完全可达性

• 题目链接：105.有向图的完全可达性
• 文档讲解：代码随想录
• 视频讲解：图论：这次我们能到达有向图的所有节点吗？| 深度优先搜索 | 卡码网：105. 有向图的完全联通
• 状态：本题用邻接表存储图，深搜和广搜都可以，深搜+邻接表很方便。

2.1 解题小结

都说递归伴随着回溯，但本题求图的可达性不需要回溯，找路径要回溯。

▶

105.有向图的完全可达性

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        boolean[] visited = new boolean[n + 1];
        List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i < n + 1; i++) {
            graph.add(new LinkedList<>());
        }
        while (k-- > 0) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            graph.get(s).add(t);
        }

        dfs(graph, 1, visited);
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }

    private static void dfs(List<LinkedList<Integer>> graph, int node, boolean[] visited) {
        if (visited[node]) return;
        visited[node] = true;
        for (int n : graph.get(node)) {
            dfs(graph, n, visited);
        }
    }
}

106.岛屿的周长

• 题目链接：106.岛屿的周长
• 文档讲解：代码随想录
• 视频讲解：图论：这次的岛屿问题有点简单了。。 卡码网：106.岛屿的周长
• 状态：哇，简单题也没做出来。本题周长只要考虑两个因素，周围是否是边界或水域。

3.1 解题分析

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是水域，则说明是一条边；如果该陆地上下左右的空格出界了，则说明是一条边。

3.2 解题小结

▶

106.岛屿的周长

import java.util.*;

public class Main {

    static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        int res = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        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 nearX = i + dir[k][0];
                        int nearY = j + dir[k][1];
                        if (nearX < 0 || nearX >= n || nearY < 0 || nearY >= m || grid[nearX][nearY] == 0) {
                            res++;
                        }
                    }
                }
            }
        }
        System.out.println(res);
    }
}

4. 今日收获

• 追平进度！！
• 学习时长：3小时