华为机试9.1（通信/射频算法岗）

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Description
 * 思路：从起点到终点
 * 1.BFS
 * 2.加一个判断当前层数的变量count:
 *      若count为奇数：走一步
 *      若count为偶数，走两步
 */
public class Main {
    //走一步
    private static int[][] Direction1 = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    //走两步
    private static int[][] Direction2 = new int[][]{{-2,0},{0,2},{2,0},{0,-2}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();//写入矩阵的行
        int N = sc.nextInt();//写入矩阵的列
        int[][] nums = new int[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                nums[i][j] = sc.nextInt();//输入矩阵
            }
        }

        int res = solution(nums);
        System.out.println(res);


    }

    public static int solution(int[][] nums){
        int row = nums.length;
        int col = nums[0].length;

        boolean[][] visited = new boolean[row][col];
        Queue<int[]> queue = new LinkedList<>();//队列来记录矩阵的索引，有数组表示[i,j]
        queue.offer(new int[]{0,0});//队列的初始化，将起点(0,0)放进去
        int count=0;//记录层数

        while(!queue.isEmpty()){
            int size = queue.size();
            count ++;

            for(int i=0;i<size;i++){
                int[] tmp = queue.poll();

                //count为奇数时，走一步
                if(count % 2 != 0){
                    for(int[] edge : Direction1){
                        int newx = edge[0] + tmp[0];
                        int newy = edge[1] + tmp[1];

                        if(isValid(newx,newy,nums) && !visited[newx][newy] && nums[newx][newy] == 1){
                            if(newx == row-1 && newy == col-1){
                                return count;
                            }
                            visited[newx][newy] = true;
                            queue.offer(new int[]{newx,newy});
                        }
                    }
                }
                
                //count为奇数时，走一步
                if(count % 2 == 0){
                    for(int[] edge : Direction2){
                        int newx = edge[0] + tmp[0];
                        int newy = edge[1] + tmp[1];

                        if(isValid(newx,newy,nums) && !visited[newx][newy] && nums[newx][newy] == 1){
                            if(newx == row-1 && newy == col-1){
                                return count;
                            }
                            visited[newx][newy] = true;
                            queue.offer(new int[]{newx,newy});
                        }
                    }
                }
            }


        }

        return 0;


    }

    static boolean isValid(int i,int j,int[][] nums){
        int row = nums.length;
        int col = nums[0].length;

        if(i<0 || i>=row || j<0 || j>=col) return false;
        else return true;

    }
}
//这种写法过了75%,不知道哪里出了问题🤤

import java.util.*;

/**
 * @Description 求连通的个数
 * 输入描述：
 * 第一个数为顶点与顶点之间的连接关系数N
 * 接下来输入N行，表示两顶点之间相连
 *
 * 输出：有几个连通图
 *
 * 输入：
 * 6
 * [0 1]
 * [0 2]
 * [0 3]
 * [0 4]
 * [4 5]
 * [6 7]
 *
 * 输出：
 * 2
 * //不知道顶点个数，而且顶点是无序的，并非为0~n-1这样的,
 * 所以构造图时采用HashMap，同时记录顶点和对应的邻接表
 * @creat 2021-09-01
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashMap<Integer, Set<Integer>> adj = new HashMap<>();
        HashMap<Integer, Boolean> visited = new HashMap<>();//标记顶点是否被访问
        //构建无向图
        //1.构建顶点：
        Set<Integer> set = new HashSet<>();//去重操作
        List<Integer> list = new LinkedList<>();//存放顶点的list
        int[][] edges = new int[N][2];//获取输入数据
        
        for(int i=0;i<N;i++){
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();

            if(!set.contains(edges[i][0])){
                list.add(edges[i][0]);
                set.add(edges[i][0]);
            }
            if(!set.contains(edges[i][1])){
                list.add(edges[i][1]);
                set.add(edges[i][1]);
            }

        }

        //对每个顶点构建邻接表(初始化)：
        for(Integer g : list){
            adj.put(g,new HashSet<>());
            visited.put(g,false);
        }

        //添加顶点间的指向
        for(int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }


        //对每个顶点进行DFS遍历
        //访问当前节点标记为true

        int count=0;//记录连通图数量
        for(Integer i : list){
            if(!visited.get(i)){
                dfs(i,adj,visited);
                count++;
            }
        }

        System.out.println(count);
    }

    static void dfs(int i, HashMap<Integer, Set<Integer>> adj ,HashMap<Integer, Boolean> visited){
        visited.put(i,true);
        Set<Integer> temp = adj.get(i);//当前顶点的邻接表

        for(Integer g : temp){
            if(!visited.get(g)){
                dfs(g,adj,visited);
            }
        }

    }
}