代码随想录第五十三天| 102.沉没孤岛 105.有向图的完全可达性 106.岛屿的周长

字符串转换序列

题目描述

给定一个字符串 beginStr 和一个字符串 endStr，以及一个字典 strList。找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。转换规则如下：

1. 序列中第一个字符串是 beginStr。
2. 序列中最后一个字符串是 endStr。
3. 每次转换只能改变一个字符。
4. 转换过程中的中间字符串必须是字典 strList 中的字符串，且每个字符串只能使用一次。

如果不存在这样的转换序列，返回 0。

解题思路

使用广度优先搜索（BFS）来寻找最短路径：

1. 初始化：将 beginStr 入队，并标记为已访问。
2. 逐层搜索：每次从队列中取出一个字符串，尝试改变其中的每一个字符，生成所有可能的变体。
3. 检查变体：如果生成的变体在字典中且未被访问过，则将其入队，并标记为已访问。
4. 结束条件：如果生成的变体是 endStr，直接返回当前路径长度 + 1。
5. 层标记：使用 null 标记每一层的结束，当处理完一层后，路径长度加 1。

代码实现

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();
        List<String> wordList = new ArrayList<>();
        wordList.add(beginStr);
        wordList.add(endStr);
        for (int i = 0; i < n; i++) {
            wordList.add(scanner.nextLine());
        }
        int count = bfs(beginStr, endStr, wordList);
        System.out.println(count);
    }

    /**
     * 广度优先搜索-寻找最短路径
     */
    public static int bfs(String beginStr, String endStr, List<String> wordList) {
        int len = 1;
        Set<String> set = new HashSet<>(wordList);
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        visited.add(beginStr);
        q.add(beginStr);
        q.add(null); // 用于标记每一层的结束
        while (!q.isEmpty()) {
            String node = q.remove();
            // 上一层结束，若下一层还有节点进入下一层
            if (node == null) {
                if (!q.isEmpty()) {
                    len++;
                    q.add(null);
                }
                continue;
            }
            char[] charArray = node.toCharArray();
            // 寻找邻接节点
            for (int i = 0; i < charArray.length; i++) {
                // 记录旧值，用于回滚修改
                char old = charArray[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    charArray[i] = j;
                    String newWord = new String(charArray);
                    if (set.contains(newWord) && !visited.contains(newWord)) {
                        q.add(newWord);
                        visited.add(newWord);
                        // 找到结尾
                        if (newWord.equals(endStr)) return len + 1;
                    }
                }
                charArray[i] = old; // 回滚修改
            }
        }
        return 0;
    }
}

有向图的完全可达性

题目描述

给定一个有向图，包含 N 个节点，节点编号分别为 1，2，…，N。现从 1 号节点开始，如果可以从 1 号节点通过边到达任何其他节点，则输出 1，否则输出 -1。

解题思路

深度优先搜索（DFS）

1. 初始化：创建一个布尔数组 visited，用于记录每个节点是否被访问过。
2. 递归遍历：从节点 1 开始，递归访问其所有邻接节点。对于每个未访问的邻接节点，标记为已访问，并继续递归。
3. 检查连通性：遍历完成后，检查 visited 数组中是否有未访问的节点。如果有，则说明无法从节点 1 到达所有节点，返回 -1；否则返回 1。

广度优先搜索（BFS）

1. 初始化：创建一个布尔数组 visited，用于记录每个节点是否被访问过。创建一个队列，将起始节点 1 入队，并标记为已访问。
2. 队列处理：从队列中取出节点，遍历其所有邻接节点。对于每个未访问的邻接节点，标记为已访问并入队。
3. 检查连通性：当队列为空时，遍历完成。检查 visited 数组中是否有未访问的节点。如果有，则返回 -1；否则返回 1。

深搜与广搜对比

代码实现

import java.util.*;

public class Main {
    public static List<List<Integer>> adjList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertices_num = sc.nextInt();
        int line_num = sc.nextInt();
        
        // 初始化邻接表
        for (int i = 0; i < vertices_num; i++) {
            adjList.add(new LinkedList<>());
        }
        
        // 构建邻接表
        for (int i = 0; i < line_num; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            adjList.get(s - 1).add(t - 1);
        }
        
        boolean[] visited = new boolean[vertices_num];
        
        // 可以选择使用 DFS 或 BFS，这里使用 BFS
        bfs(visited, 0);

        // 检查是否所有节点都被访问过
        for (int i = 0; i < vertices_num; i++) {
            if (!visited[i]) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }

    // 深度优先搜索
    public static void dfs(boolean[] visited, int key) {
        if (visited[key]) {
            return;
        }
        visited[key] = true;
        List<Integer> nextKeys = adjList.get(key);
        for (int nextKey : nextKeys) {
            dfs(visited, nextKey);
        }
    }

    // 广度优先搜索
    public static void bfs(boolean[] visited, int key) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(key);
        visited[key] = true;
        
        while (!queue.isEmpty()) {
            int curKey = queue.poll();
            List<Integer> nextKeys = adjList.get(curKey);
            for (int nextKey : nextKeys) {
                if (!visited[nextKey]) {
                    queue.add(nextKey);
                    visited[nextKey] = true;
                }
            }
        }
    }
}

岛屿的周长

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。

解题思路

1. 遍历矩阵：逐个检查矩阵中的每个单元格。
2. 检查陆地单元格：当发现陆地单元格（值为 1）时，检查其上下左右四个方向的相邻单元格。
3. 计算周长贡献：对于每个陆地单元格的相邻方向，如果相邻单元格是水（值为 0）或者超出矩阵边界，则该方向对周长贡献 1。
4. 标记访问：使用一个二维布尔数组 visited 来标记已经访问过的陆地单元格，避免重复计算。

代码实现

import java.util.*;

public class Main {
    public static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    for (int k = 0; k < 4; k++) {
                        int x = i + dir[k][0];
                        int y = j + dir[k][1];
                        if (x < 0 || y < 0 || x >= m || y >= n) {
                            res++;
                            continue;
                        }
                        if (grid[x][y] == 0) {
                            res++;
                        }
                    }
                }
            }
        }
        
        System.out.println(res);
    }
}