代码随想录Day67(图论 part04)

110.字符串接龙

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

思路：没有思路

答案

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        String beginStr = scanner.next();
        String endStr = scanner.next();
        
        Set<String> strSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            strSet.add(scanner.next());
        }
        
        System.out.println(findShortestTransformation(beginStr, endStr, strSet));
    }

    private static int findShortestTransformation(String beginStr, String endStr, Set<String> strSet) {
        // 记录strSet里的字符串是否被访问过，同时记录路径长度
        Map<String, Integer> visitMap = new HashMap<>();
        
        // 初始化队列
        Queue<String> queue = new LinkedList<>();
        queue.add(beginStr);
        
        // 初始化visitMap
        visitMap.put(beginStr, 1);

        while (!queue.isEmpty()) {
            String word = queue.poll();
            int pathLength = visitMap.get(word); // 这个字符串在路径中的长度
            
            // 开始在这个str中，挨个字符去替换
            for (int i = 0; i < word.length(); i++) {
                char[] newWordArray = word.toCharArray();
                
                // 遍历26个字母
                for (char j = 'a'; j <= 'z'; j++) {
                    newWordArray[i] = j;
                    String newWord = new String(newWordArray);
                    
                    if (newWord.equals(endStr)) { // 发现替换字母后，字符串与终点字符串相同
                        return pathLength + 1; // 找到了路径
                    }
                    
                    // 字符串集合里出现了newWord，并且newWord没有被访问过
                    if (strSet.contains(newWord) && !visitMap.containsKey(newWord)) {
                        // 添加访问信息，并将新字符串放到队列中
                        visitMap.put(newWord, pathLength + 1);
                        queue.add(newWord);
                    }
                }
            }
        }
        
        // 没找到输出0
        return 0;
    }
}

小结

• 使用  Set<String>   存储字符串
• 使用  Map<String, Integer>  记录是否访问过,以及路径长度
• 通过queue来存储遍历过的字符串,从beginStr开始,每次替换一个字符,要是替换后的字符串存在于set中,就将该字符串记录为已访问,并将字符串放入到queue中

105.有向图的完全可达性

题目：105. 有向图的完全可达性 (kamacoder.com)

思路：从1出发,进行深搜,走完所有路径,看是否能够到达所有节点

尝试(运行出错）

import java.util.*;
 
public class Main {
    private static List<List<Integer>> adjList;
    private static List<List<Integer>> allPaths;
    private static int target;
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        adjList = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            adjList.get(s).add(t);
        }
        
        
        for(int i =2; i<=n; i++){
            target = i;
            allPaths = new ArrayList<>();
            List<Integer> currentPath = new ArrayList<>();
            currentPath.add(1);
            findAllPaths(1, currentPath);
            if(allPaths.isEmpty()){
                 System.out.println("-1");
            }
        }
         System.out.println("1");
        
        scanner.close();
    }
    
    private static void findAllPaths(int currentNode, List<Integer> currentPath) {
        if (currentNode == target) {
            allPaths.add(new ArrayList<>(currentPath));
            return;
        }
        
        for (int nextNode : adjList.get(currentNode)) {
            currentPath.add(nextNode);
            findAllPaths(nextNode, currentPath);
            currentPath.remove(currentPath.size() - 1);
        }
    }
    

}

答案

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 节点数量
        int m = scanner.nextInt(); // 边的数量

        // 节点编号从1到n，所以申请 n+1 这么大的数组
        List<List<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 读取边的信息并构建邻接表
        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            graph.get(s).add(t);
        }

        // 初始化访问数组
        boolean[] visited = new boolean[n + 1];
        dfs(graph, 1, visited);

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

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

小结

通过递归, 把所有路径跑一遍, 之后再检查是否所有的节点都有被访问到, 此处不需要回溯

106.岛屿的周长

题目：106. 岛屿的周长 (kamacoder.com)

思路：逐个遍历1，计算每个1跟临近的0所形成的边界，加起来，就是周长

尝试（示例输出正确，提交后输出错误）

import java.util.*;

class Main{
    public static int n;
    public static int m;
    public static int[][] grid;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        grid = new int[n][m];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                grid[i][j] = scanner.nextInt();   
            }
        }
        int maxArea = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                maxArea+=count(i,j);   
            }
        }
        System.out.println(maxArea);
    }
    public static int count(int i,int j){
        if(grid[i][j]!=1) return 0;
        int len = 0;
        if(grid[i-1][j]==0){
            len++;
        }
        if(grid[i+1][j]==0){
            len++;
        }
        if(grid[i][j-1]==0){
            len++;
        }
        if(grid[i][j+1]==0){
            len++;
        }
        return len;
    }
}

答案

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        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();
            }
        }

        int landCount = 0; // 陆地数量
        int neighborCount = 0; // 相邻陆地的数量

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    landCount++; // 统计总的陆地数量
                    // 统计上边相邻陆地
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) neighborCount++;
                    // 统计左边相邻陆地
                    if (j - 1 >= 0 && grid[i][j - 1] == 1) neighborCount++;
                    // 下边和右边的相邻陆地不统计是为了避免重复计算
                }
            }
        }

        // 计算岛屿的周长
        int perimeter = landCount * 4 - neighborCount * 2;
        System.out.println(perimeter);
    }
}

小结

注意每次只统计上边和左边的相邻陆地