Day58 算法训练营

110.字符串接龙；105.有向图的完全可达性；106.岛屿的周长；

110.字符串接龙

需要注意的点：

• 本题是bfs应用的一道题目，需要求出最短路径的长度，无需求出最短路径，因此要根据题目要求，把字典中的字符串连成图，每个节点之间如何连线？按照题目要求，若两个字符串只有一个字符不相同，则这两个字符串必相互可达，然后按照bfs，从起点到终点遍历，遍历到终点就将路径长度返回即可：

  

• 要注意next()、nextInt()、nextLine()等方法的区别：next()和nextInt不会忽略换行符，换行符会留在输入流中，但当nextInt()连用时，nextInt()会自动忽略换行符，读取下一个int；nextLine()会忽略换行符，直接读取返回一行的内容

AC代码：

public class StrSolitaire {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String beginStr = sc.next();
        String endStr = sc.next();
        sc.nextLine();
        List<String> wordList = new ArrayList<>();
        wordList.add(beginStr);
        wordList.add(endStr);
        for (int i = 0; i < n; i++) {
            wordList.add(sc.nextLine());
        }
        int result = bfs(beginStr, endStr, wordList);
        System.out.println(result);
    }

    private static int bfs(String beginStr, String endStr, List<String> wordList) {
        int len = 1;
        Queue<String> queue = new LinkedList<>();
        HashSet<String> wordSet = new HashSet<>(wordList);
        HashSet<String> visited = new HashSet<>();
        queue.add(beginStr);
        queue.add(null);
        visited.add(beginStr);
        while (!queue.isEmpty()){
            String node = queue.poll();
            if (node == null){
                if (!queue.isEmpty()){
                    len += 1;
                    queue.add(null);
                }
                continue;
            }
            char[] nodeChars = node.toCharArray();
            for (int i = 0; i < nodeChars.length; i++) {
                char old = nodeChars[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    nodeChars[i] = j;
                    String newNode = new String(nodeChars);
                    if (wordSet.contains(newNode) && !visited.contains(newNode)){
                        queue.add(newNode);
                        visited.add(newNode);
                        if (newNode.equals(endStr)) return len + 1;
                    }
                }
                nodeChars[i] = old;
            }
        }
        return 0;
    }
}

105.有向图的完全联通

需要注意的点：

• 本题初始思路果真陷入了dfs的两种写法，即visited数组究竟在哪里被赋值为true，是否需要回溯等问题。实际上，在递归中，是处理当前访问的节点，还是处理下一个要访问的节点，这决定了终止条件怎么写：

  • 如果是处理当前访问的节点，当前节点如果是true，说明已经访问过该节点，直接终止本层递归，如果不是true，则将此节点置为true，开始本层递归

    void dfs(int[][] graph, int x, boolean[] visited){
        if(visited[x]) return;
        visited[x] = true;
        for(int i = 1; i < graph.length; i++){
            if(graph[x][i] == 1) dfs(graph, i, visited);
        }
    }
    

  • 如果是处理下一个要访问的节点，那么就要在处理出发路径时对节点进行处理，这样就不需要终止条件，而是在搜索下一个节点的时候，直接判断下一个节点是否是我们要搜的节点

    void dfs(int[][] graph, int x, boolean[] visited){
        for(int i = 1; i < graph.length; i++){
            if(graph[x][i] == 1 && !visited[i]){
                visited[i] = true;
                dfs(graph, i, visited);
            }
        }
    }
    

• 另外，还要思考为何本题没有回溯的步骤，原因在于本题是要求判断节点1是否能到达所有的节点，只需将遍历过的节点一律都标记上即可。当需要搜索出一条可行路径时，才需要回溯的操作，因为此时不回溯，将无法回头

AC代码：

public class ConnectivityGraph {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = 1;
        }
        boolean[] visited = new boolean[n + 1];
        dfs(graph, visited, 1);

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

    private static void dfs(int[][] graph, boolean[] visited, int x) {
        if (visited[x]) return;
        visited[x] = true;
        for (int i = 1; i < graph.length; i++) {
            if (graph[x][i] == 1){
                dfs(graph, visited, i);
            }
        }
    }
}

106.岛屿的周长

需要注意的点：

• 本题有两种思路可以AC，但Java语言在平台上提交是时间超限，C++就没问题，都是一样的思路

• 方法一：从一个陆地节点开始，向上下左右四个方向访问，若访问到水域或边缘，则说明该边会被计入到周长当中，则result自增，将graph遍历完后返回result即可

• 方法二：从一个陆地节点开始，判断向上方向和向左方向是否为陆地，若为陆地，说明当前陆地节点和方向陆地节点是两个相邻节点，相邻节点有2条边是重叠的，故最后应该将所有的陆地节点 * 4算出总边长数，再减去重叠的节点边长数（重叠陆地节点 * 2），遍历结束将该结果返回即可

AC代码：

// 方法一
public class IslandPerimeter {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        int result = 0;
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1){
                    for (int k = 0; k < 4; k++) {
                        int nextX = i + dir[k][0];
                        int nextY = j + dir[k][1];
                        if (nextX < 0 || nextX >= graph.length || nextY < 0 || nextY >= graph[0].length || graph[nextX][nextY] == 0) result += 1;
                    }
                }
            }
        }
        System.out.println(result);
    }
}

// 方法二
public class IslandPerimeterII {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        int sum = 0;
        int cover = 0;
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1){
                    sum += 1;
                    if (i - 1 >= 0 && graph[i - 1][j] == 1) cover += 1;
                    if (j - 1 >= 0 && graph[i][j - 1] == 1) cover += 1;
                }
            }
        }
        System.out.println(sum * 4 - cover * 2);
    }
}