蓝桥杯基础知识巩固--矩阵填数和BFS的应用

客官°小女子只卖身不卖艺 2022-11-18 15:00 107阅读 0赞

一、前言

> 今天，进行了近两年的蓝桥杯JavaB组真题整理，发现存在严重的基础薄弱问题。于是做了以下的基础知识巩固梳理。

二、代码

矩阵填数

package lq.questions.consolidate;
    
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.concurrent.atomic.AtomicReference;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    /** * @AUTHOR LYF * @DATE 2021/4/13 * @VERSION 1.0 * @DESC * 矩阵的填数以及遍历 * 采用链表+String构成矩阵 */
    public class Count { 
    
        static List<String> lists = new ArrayList<>();
        static { 
            // 读入数据
            try{ 
                InputStream ips = new FileInputStream("E:\\IdeaProjects\\java-base\\src\\main\\java\\lq\\questions\\consolidate\\files\\Find2020");
                InputStreamReader isr = new InputStreamReader(ips);//读入输入流
                BufferedReader br = new BufferedReader(isr);//缓存读取
    
                String temp = null;
                while((temp=br.readLine())!=null){ 
                    lists.add(temp);
                }
    
                // 验证结果
                System.out.println("读入数据为:");
                lists.stream().forEach(System.out::println);
    
            }catch (Exception e){ 
                e.printStackTrace();
            }
        }
    
        // 寻找2020
        // 遍历行列、斜方向
        // 关于斜方向如何遍历？
        // 截取从(0,0)-直到row为最大或者列为最大或者字符串长度判断
    
        // 判断字符串含有的2020的数量
        Integer count2020(String str){ 
            String regex = "2020";
            Pattern p = Pattern.compile(regex);
            Matcher m =p.matcher(str);
            int count =0;
            while(m.find())
            { 
                count++;
                System.out.println("在"+m.start()+"匹配到2020");
            }
            return count;
        }
    
        // 进行总体计数
        void handleFind2020(){ 
    
            // 原子计数，Atomic了解
            AtomicReference<Integer> sum1 = new AtomicReference<>(0);
            // 每一行计数,即lists的遍历
            lists.stream().forEach((str)->{ 
                sum1.updateAndGet(v -> v + count2020(str));
            });
    
            // 处理列
            int len = lists.get(0).length();
            String[] rowStr = new String[len];
            Arrays.fill(rowStr,"");
            for(int i =0;i<lists.size();i++){ 
                for(int j=0;j<len;j++){ 
                    rowStr[j]=rowStr[j]+lists.get(i).charAt(j);
                }
            }
            for(String str :rowStr){ 
                sum1.updateAndGet(v->v+count2020(str));//{}则有返回值
            }
    
            // 斜方向！！
            // 突然发现还是矩阵方便处理，于是转换为矩阵
            Character[][] map = new Character[lists.size()][len];
            int row=lists.size(),col=len;
            for(int i =0;i<lists.size();i++){ 
                for(int j=0;j<len;j++) { 
                    map[i][j] = lists.get(i).charAt(j);
                }
            }
    
            // 从左斜方向到右斜方向，确定起点和终点以及变化规则
            // 起点: (rowMax-字符串"2020"len,0) 终点:(0,colMax-"2020".length())
            // 规则:截取点开始到无法截取的长度，点的变化规则i--到0,j
    
            List<String> biasList=new ArrayList<>();
    
            int i=row-4,j=0;
    
            while(i!=0||j!=len-4){ //字符串开始的点(i,j)，终点结束
    
                String temp ="";
                int vaI=i,vaJ=j;
                while(vaI<row&&vaJ<col){ 
                    temp=temp+map[vaI++][vaJ++];
                }
                biasList.add(temp);
    
                //起点移动
                if(i!=0){ 
                    i--;
                }else{ 
                    j++;
                }
            }
    
            int vaI=i,vaJ=j;
            String temp=""; //最后一个点
            while(vaI<row&&vaJ<col){ 
                temp=temp+map[vaI++][vaJ++];
            }
    
            biasList.add(temp);
            System.out.println("测试:");
            biasList.stream().forEach(System.out::println);
        }
    
        // 相关补充
        // 蛇形填数
        int[][] map = new int[41][41];//方便验证
        void printRs(){ 
            System.out.println("验证:");
            for(int row=0;row<40;row++){ 
                for(int col=0;col<40;col++){ 
                    System.out.print(map[row][col]+" ");
                }
                System.out.println();
            }
        }
    
        void handleSnake(){ 
    
            int i=0,j=0,count=1;
    
            while(i!=19||j!=19){ 
                map[i][j]=count;
    
                if(i==0){ // 行为0则col++
                    map[0][++j]=++count;
                }
    
                while(j>0){ 
                    map[++i][--j]=++count;
                    if(i==19&&j==19){ 
                       printRs();
                        return;
                    }
                }
    
                if(j==0){ 
                    map[++i][0]=++count;
                }
    
                while (i>0){ 
                    map[--i][++j]=++count;
                    if(i==19&&j==19){ 
                       printRs();
                        return;
                    }
                }
            }
        }
    
        int len=5;// 矩阵长度
        int[][] map2=new int[len][len];
        void writeMap(int endRow,int endCol){ 
    // Arrays.fill(map2,0);
            for(int i =0;i<len;i++){ 
                Arrays.fill(map2[i],0);
            }
            int row=0,col=0,count=1;
            while(row!=endRow||col!=endCol){ 
                // 向右进行填数
                while(col<len&&map2[row][col]==0){ //注意需要先进行边界判断
                    map2[row][col++]=count++;
                }
                col--;//col回退
                row++;// 下一列
                while (row<len&&map2[row][col]==0){ 
                    map2[row++][col]=count++;
                }
                row--;//row回退
                col--;//向左一列
                while (col>=0&&map2[row][col]==0){ 
                    map2[row][col--]=count++;
                }
                col++;
                row--;
                while(row>=0&&map2[row][col]==0){ 
                    map2[row--][col]=count++;
                }
                row++;
                col++;
            }
            // 处理最后一个数
            map2[endRow][endCol] =count;
            print();
        }
        void print(){ 
            for(int i =0;i<len;i++){ 
                for(int j=0;j<len;j++){ 
                    System.out.print(map2[i][j]+" ");
                }
                System.out.println();
            }
        }
        // 回形填写矩阵
        void handleCircle(){ 
    
            // 与蛇形填数类似
            // 起点（0，0）
            // 终点（ 奇数则是 (len/2,len/2),偶数则是 (len/2-1,len/2-1)
            // 规则 当遇到未进行填写就递进（ col++直到下一个为已填或者边界，col保持不变，row++到已填或者边界，
    
            if(len%2==0){ 
                writeMap(len/2-1,len/2-1);
            }else{ 
                writeMap(len/2,len/2);
            }
        }
    
        public static void main(String[]args){ 
            Count c= new Count();
            c.handleCircle();
        }
    
    }

BFS的简单应用（其实之前已经做过，今天只是再次熟悉）

package lq.questions.consolidate;
    
    
    import lq.questions.consolidate.domain.Point;
    
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.util.*;
    
    /** * @AUTHOR LYF * @DATE 2021/4/13 * @VERSION 1.0 * @DESC */
    public class Graph { 
    
        // 前置:BFS\DFS
        // 连通性和深搜 见lq\base\structrure\graph\BFS.java
    
        // 模拟数据
        static int[][]map = new int[100][100];//连通性
        static int[][]maze= new int[100][100];//迷宫
        // 读取测试文件
        static void printMap(int command){ 
    // if(command==1){ 
    // for(int i =0;i<)
    // }else { 
    //
    // }
        }
        static { 
    
            try{ 
                String path = "E:\\IdeaProjects\\java-base\\src\\main\\java\\lq\\questions\\consolidate\\files\\maze";
                InputStream ips = new FileInputStream(path);
                InputStreamReader isr = new InputStreamReader(ips);
                BufferedReader br =  new BufferedReader(isr);
    
                int row=0,col=0;
                String line = "";
                while((line=br.readLine())!=null){ 
                    col=line.length();
                    for(int i =0;i<line.length();i++){ 
                      maze[row][i]=Integer.valueOf(line.substring(i,i+1));
                    }
                    row++;
                }
    
                for(int i=0;i<row;i++){ 
                    for(int j =0;j<col;j++){ 
                        System.out.print(maze[i][j]+" ");
                    }
                    System.out.println();
                }
    
            }catch (Exception e){ 
                e.printStackTrace();
            }
        }
    
        // BFS => 最短路径，如何走
        // 迷宫问题（可行》最短路径》路径》 BFS）
        // 定义Point
        // 设置方向量方便进行四个放行广度搜索
        int toRow[]={ 0,-1,0,1};
        int toCol[]={ 1,0,-1,0}; // 右下左上
    
        // 广搜
        // 重点理解，最先搜到的即为最短的，也就相当于树的深度。另外采用队列进行先加入的先进行搜索
        void bfs(){ 
    
            Queue<Point> queue = new ArrayDeque<Point>();
    
            // 启动
            //Point startP = new Point(0,0,null,1);// 若在类的属性中进行赋值对象则不能这样写
            Point startP = new Point(0,0,null,1);
    
            queue.add(startP);//添加启动
            while(!queue.isEmpty()){  //未找完则一直寻找，若找到目标点则进行退出
    
                Point cur = queue.poll();
    
                if(cur.getI()== 3&&cur.getJ()==5){ 
                    // 找到目标点
                    // cur就是一个链表头进行逆向打印即可，size()
                    List<Point> list = new ArrayList<>();
    
                    Point p = cur;
                    while(p!=null)
                    { 
                        list.add(p);
                        p=p.getPre();
                    }
    
                    System.out.println("最短路径长度:"+list.size());
                    System.out.println("最短路径:");
    
                    for(int i =list.size()-1;i>=0;i--){ 
                        System.out.print("("+list.get(i).getI()+","+list.get(i).getJ()+")=>");
                    }
    
                    return;
                }
    
                // 遍历四个方向，寻找可进行加入的点
                for(int i = 0;i<4;i++){ 
                    int nextI = cur.getI()+toRow[i];
                    int nextJ = cur.getJ()+toCol[i];
                    // 先进行边界判断
                    if(nextI>=0&&nextJ>=0&&nextI<4&&nextJ<6&&maze[nextI][nextJ]==0){ 
                        Point next=new Point(nextI,nextJ,cur,0);//其实没有必要设立val,可以附加其他信息
                        queue.add(next);
                        // 需要标记当前点进行标记了吗
                        // 需要吧，因为加入队列已经标记搜索过该地方，其他能够搜索到该地方也只能慢于此，所以说没有必要在进行搜索了
                        // 那么思考，如何考虑所有的路径呢？？，就无需设立吗
                        maze[nextI][nextJ]=1;
                    }
                }
            }
        }
    
    
        // 连通性判断
        // 思路进行遍历矩阵，发现1就进行深搜，并将其搜索的点进行visited二维数组标记
        static boolean[][] visited=new boolean[4][6];
        static { 
            for(int i =0;i<4;i++){ 
                Arrays.fill(visited[i],false);
            }
        }
    
    
        // 无需前驱
        class Point2{ 
            int i,j;
    
            public Point2() { 
            }
    
            public Point2(int i, int j) { 
                this.i = i;
                this.j = j;
            }
    
            public int getI() { 
                return i;
            }
    
            public void setI(int i) { 
                this.i = i;
            }
    
            public int getJ() { 
                return j;
            }
    
            public void setJ(int j) { 
                this.j = j;
            }
        }
    
    
        // 深搜起点
        void handleBfs(int startI,int startJ){ 
    
            Point2 startP = new Point2(startI,startJ);
            Queue<Point2> queue = new ArrayDeque<>();
            queue.add(startP);
            while (!queue.isEmpty()){ 
    
                Point2 cur = queue.poll();
    
                for(int i =0;i<4;i++){ 
                    int nextI = cur.getI()+toRow[i];
                    int nextJ = cur.getJ()+toCol[i];
    
                    if(nextI<4&&nextJ<6&&nextI>=0&&nextJ>=0&&maze[nextI][nextJ]==1){ 
                        Point2 next = new Point2(nextI,nextJ);
                        queue.add(next);
                        System.out.println("进入在("+nextI+","+nextJ+")深搜");
                        maze[nextI][nextJ]=0;//若不设置此处未0，会进行一直搜索，死循环，或者判断时使用visited数组进行判断
                       // this.visited[nextI][nextJ]=true;//直接在maze上进行标记呢？？影响下次深搜》？
                        // 其实没有必要设立visited，直接使用maze即可，搜过的地方直接跳过
                    }
                }
                if(queue.size()==0)
                { 
                    return;
                }
            }
    
        }
    
        // 判断联通的岛屿（处理大量时，此处简单小量数据只做展示）
        void connectivity(){ 
            int count=0;
            for(int i =0;i<4;i++){ 
                for(int j =0;j<6;j++){ 
                    if(maze[i][j]==1){ //未访问则进行深搜，且是在岛屿上 &&this.visited[i][j]==false
                        handleBfs(i,j);
    
                        count++;
                    }
                }
            }
            System.out.println("岛屿数"+count);
        }
    
    
    
        public static void main(String[]args){ 
            Graph g= new Graph();
            g.connectivity();
        }
    
    
        // 七段码
    }

七段码（蓝桥杯）  
排列组合时可以递归简化代码

package lq.questions.consolidate.graph;
    
    
    import lq.questions.consolidate.domain.Point;
    
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.util.*;
    
    /** * @AUTHOR LYF * @DATE 2021/4/13 * @VERSION 1.0 * @DESC */
    public class Graph { 
    
        // 前置:BFS\DFS
        // 连通性和深搜 见lq\base\structrure\graph\BFS.java
    
        // 模拟数据
        static int[][]map = new int[100][100];//连通性
        static int[][]maze= new int[100][100];//迷宫
        // 读取测试文件
        static void printMap(int command){ 
    // if(command==1){ 
    // for(int i =0;i<)
    // }else { 
    //
    // }
        }
        static { 
    
            try{ 
                String path = "E:\\IdeaProjects\\java-base\\src\\main\\java\\lq\\questions\\consolidate\\files\\maze";
                InputStream ips = new FileInputStream(path);
                InputStreamReader isr = new InputStreamReader(ips);
                BufferedReader br =  new BufferedReader(isr);
    
                int row=0,col=0;
                String line = "";
                while((line=br.readLine())!=null){ 
                    col=line.length();
                    for(int i =0;i<line.length();i++){ 
                      maze[row][i]=Integer.valueOf(line.substring(i,i+1));
                    }
                    row++;
                }
    
                for(int i=0;i<row;i++){ 
                    for(int j =0;j<col;j++){ 
                        System.out.print(maze[i][j]+" ");
                    }
                    System.out.println();
                }
    
            }catch (Exception e){ 
                e.printStackTrace();
            }
        }
    
        // BFS => 最短路径，如何走
        // 迷宫问题（可行》最短路径》路径》 BFS）
        // 定义Point
        // 设置方向量方便进行四个放行广度搜索
        int toRow[]={ 0,-1,0,1};
        int toCol[]={ 1,0,-1,0}; // 右下左上
    
        // 广搜
        // 重点理解，最先搜到的即为最短的，也就相当于树的深度。另外采用队列进行先加入的先进行搜索
        void bfs(){ 
    
            Queue<Point> queue = new ArrayDeque<Point>();
    
            // 启动
            //Point startP = new Point(0,0,null,1);// 若在类的属性中进行赋值对象则不能这样写
            Point startP = new Point(0,0,null,1);
    
            queue.add(startP);//添加启动
            while(!queue.isEmpty()){  //未找完则一直寻找，若找到目标点则进行退出
    
                Point cur = queue.poll();
    
                if(cur.getI()== 3&&cur.getJ()==5){ 
                    // 找到目标点
                    // cur就是一个链表头进行逆向打印即可，size()
                    List<Point> list = new ArrayList<>();
    
                    Point p = cur;
                    while(p!=null)
                    { 
                        list.add(p);
                        p=p.getPre();
                    }
    
                    System.out.println("最短路径长度:"+list.size());
                    System.out.println("最短路径:");
    
                    for(int i =list.size()-1;i>=0;i--){ 
                        System.out.print("("+list.get(i).getI()+","+list.get(i).getJ()+")=>");
                    }
    
                    return;
                }
    
                // 遍历四个方向，寻找可进行加入的点
                for(int i = 0;i<4;i++){ 
                    int nextI = cur.getI()+toRow[i];
                    int nextJ = cur.getJ()+toCol[i];
                    // 先进行边界判断
                    if(nextI>=0&&nextJ>=0&&nextI<4&&nextJ<6&&maze[nextI][nextJ]==0){ 
                        Point next=new Point(nextI,nextJ,cur,0);//其实没有必要设立val,可以附加其他信息
                        queue.add(next);
                        // 需要标记当前点进行标记了吗
                        // 需要吧，因为加入队列已经标记搜索过该地方，其他能够搜索到该地方也只能慢于此，所以说没有必要在进行搜索了
                        // 那么思考，如何考虑所有的路径呢？？，就无需设立吗
                        maze[nextI][nextJ]=1;
                    }
                }
            }
        }
    
    
        // 连通性判断
        // 思路进行遍历矩阵，发现1就进行深搜，并将其搜索的点进行visited二维数组标记
        static boolean[][] visited=new boolean[4][6];
        static { 
            for(int i =0;i<4;i++){ 
                Arrays.fill(visited[i],false);
            }
        }
    
    
        // 无需前驱
        class Point2{ 
            int i,j;
    
            public Point2() { 
            }
    
            public Point2(int i, int j) { 
                this.i = i;
                this.j = j;
            }
    
            public int getI() { 
                return i;
            }
    
            public void setI(int i) { 
                this.i = i;
            }
    
            public int getJ() { 
                return j;
            }
    
            public void setJ(int j) { 
                this.j = j;
            }
        }
    
    
        // 深搜起点
        void handleBfs(int startI,int startJ){ 
    
            Point2 startP = new Point2(startI,startJ);
            Queue<Point2> queue = new ArrayDeque<>();
            queue.add(startP);
            while (!queue.isEmpty()){ 
    
                Point2 cur = queue.poll();
    
                for(int i =0;i<4;i++){ 
                    int nextI = cur.getI()+toRow[i];
                    int nextJ = cur.getJ()+toCol[i];
    
                    if(nextI<4&&nextJ<6&&nextI>=0&&nextJ>=0&&maze[nextI][nextJ]==1){ 
                        Point2 next = new Point2(nextI,nextJ);
                        queue.add(next);
                        System.out.println("进入在("+nextI+","+nextJ+")深搜");
                        maze[nextI][nextJ]=0;//若不设置此处未0，会进行一直搜索，死循环，或者判断时使用visited数组进行判断
                       // this.visited[nextI][nextJ]=true;//直接在maze上进行标记呢？？影响下次深搜》？
                        // 其实没有必要设立visited，直接使用maze即可，搜过的地方直接跳过
                    }
                }
                if(queue.size()==0)
                { 
                    return;
                }
            }
    
        }
    
        // 判断联通的岛屿（处理大量时，此处简单小量数据只做展示）
        void connectivity(){ 
            int count=0;
            for(int i =0;i<4;i++){ 
                for(int j =0;j<6;j++){ 
                    if(maze[i][j]==1){ //未访问则进行深搜，且是在岛屿上 &&this.visited[i][j]==false
                        handleBfs(i,j);
    
                        count++;
                    }
                }
            }
            System.out.println("岛屿数"+count);
        }
    
    
        // 七段码 a-g分别对应0-6
        //
        // 采用矩阵判断连通性比较方便
        int[][] map3={ 
                { 0,1,0,0,0,0,1},
                { 1,0,1,0,0,1,0},
                { 0,1,0,1,0,1,0},
                { 0,0,1,0,1,0,0},
                { 0,0,0,1,0,1,1},
                { 0,1,1,0,0,0,1},
                { 1,0,0,0,1,1,0}
        };
    
        // 排列组合查看是否联通
        // 两两判断是否联通？
        void handle(){ 
            for(int i =1;i<=7;i++){ //依次判断选取1-7个的组合
            }
    
            // 选1个为7
            // 选7个为1
            // 选6个为
        }
    
    
        // 法二，抽象成点
        /* 0 0 0 0 0 0 0 0 a : (0,0)和(0,1)设置为1 判断连通性：BFS */
    
        static int[][] map7={ 
                { 0,0,0},
                { 0,0,0},
                { 0,0,0},
                { 0,0,0},
                { 0,0,0}
        };
    
        static { 
    
        }
        void writeMap(String str){ 
            System.out.println("写入棋盘"+str);
            for(int i =0;i<str.length();i++){ 
                String temp = str.substring(i,i+1);
                switch (temp){ 
                    case "a":{ map7[0][0]=map7[0][1]=map7[0][2]=1;break;}
                    case "b":{ map7[0][2]=map7[1][2]=map7[2][2]=1;break;}
                    case "c":{ map7[2][2]=map7[3][2]=map7[4][2]=1;break;}
                    case "d":{ map7[4][2]=map7[4][1]=map7[4][0]=1;break;}
                    case "e":{ map7[4][0]=map7[3][0]=map7[2][0]=1;break;}
                    case "f":{ map7[2][0]=map7[1][0]=map7[0][0]=1;break;}
                    case "g":{ map7[2][0]=map7[2][1]=map7[2][2]=1;break;}
                }
            }
    
    
            printMap7();
    
    
        }
    
        void bfs3(int startI,int startJ){ 
    
            Point2 startP = new Point2(startI,startJ);
            Queue<Point2> queue = new ArrayDeque<>();
            queue.add(startP);
    
            while (!queue.isEmpty())
            { 
                Point2 cur = queue.poll();
    
                for(int i =0;i<4;i++){ 
                    int nextI = cur.getI()+toRow[i];
                    int nextJ = cur.getJ()+toCol[i];
    
                    if(nextI>=0&&nextJ>=0&&nextI<5&&nextJ<3&&map7[nextI][nextJ]==1){ 
                        queue.add(new Point2(nextI,nextJ));
                        map7[nextI][nextJ]=0;//标记访问了
    // printMap7();
                    }
                }
            }
        }
    
        void toZero(){ 
            for(int i=0;i<5;i++){ 
                Arrays.fill(map7[i],0);
            }
        }
    
        boolean judge(String str){ 
            writeMap(str);// 填写棋盘
            int count=0;
    
            System.out.println("棋盘:");
            printMap7();
    
            for(int i =0;i<5;i++){ 
                for(int j=0;j<3;j++){ 
                    if(map7[i][j]==1){ 
                        bfs3(i,j);
                        count++;
                    }
                }
            }
            //count>1则非联通
    
            System.out.println(count);
            toZero();//归零
    
            if(count>1){ 
                return false;
            }else { 
                return true;
            }
    
        }
    
        void printMap7(){ 
            for(int i =0;i<5;i++){ 
                for(int j = 0;j<3;j++){ 
                    System.out.print(map7[i][j]+" ");
                }
                System.out.println();
            }
        }
    
        // 简化多重循环
        String simplyCirculation(String str,int n){ // 循环的次数
        return "";
        }
    
    
        // 递归处理选取问题
        void recursion(String str,int start,int end,int val){ 
            if(end-start==val){ 
                System.out.println();
            }
            for(int i=start;i<end;i++){ // 开始结束位置
    
            }
        }
    
        void handle2(){ 
    
            String str = "abcdefg";
            // 同样，1和7不用去考虑分配
    
            int sum =0;
    
            // 选取1个
            for(int i =0;i<str.length();i++){ 
                if(judge(str.substring(i,i+1))){ 
                    sum++;
                }
    
            }
    
            // 如何排列组合 ，
    
            for(int i =1;i<=7;i++){  //选取问题，无需排列
    
    
            }
    
            // 选取2个数
            for(int i =0;i<6;i++){ 
                for(int j=i+1;j<7;j++){ //多重循环
                    String strs= str.substring(i,i+1)+str.substring(j,j+1);
                    if(judge(strs)){ 
                        sum++;
                    }
                }
            }
    
            // 选取3个数
            for(int i =0;i<5;i++){ 
                for(int j=i+1;j<6;j++){ //多重循环
                    for(int k=j+1;k<7;k++){ 
                        String strs= str.substring(i,i+1)+str.substring(j,j+1)+str.substring(k,k+1);
                        if(judge(strs)){ 
                            sum++;
                        }
                    }
                }
            }
    
    
            // 选取4个数
            for(int i =0;i<4;i++){ 
                for(int j=i+1;j<5;j++){ //多重循环
                    for(int k=j+1;k<6;k++){ 
                       for(int l=k+1;l<7;l++){ 
                           String strs= str.substring(l,l+1)+str.substring(i,i+1)+str.substring(j,j+1)+str.substring(k,k+1);
                           if(judge(strs)){ 
                               sum++;
                           }
                       }
                    }
                }
            }
    
    
            // 选取5个数
            for(int i =0;i<3;i++){ 
                for(int j=i+1;j<4;j++){ //多重循环
                    for(int k=j+1;k<5;k++){ 
                        for(int l=k+1;l<6;l++){ 
                            for(int n=l+1;n<7;n++){ 
                                String strs= str.substring(n,n+1)+str.substring(l,l+1)+str.substring(i,i+1)+str.substring(j,j+1)+str.substring(k,k+1);
                                if(judge(strs)){ 
                                    sum++;
                                }
                            }
                        }
                    }
                }
            }
    
            for(int i =0;i<2;i++){ 
                for(int j=i+1;j<3;j++){ //多重循环
                    for(int k=j+1;k<4;k++){ 
                        for(int l=k+1;l<5;l++){ 
                            for(int n=l+1;n<6;n++){ 
                               for(int c=n+1;c<7;c++){ 
                                   String strs= str.substring(c,c+1)+str.substring(n,n+1)+str.substring(l,l+1)+str.substring(i,i+1)+str.substring(j,j+1)+str.substring(k,k+1);
                                   if(judge(strs)){ 
                                       sum++;
                                   }
                               }
                            }
                        }
                    }
                }
            }
    
            System.out.println(sum);
        }
    
    
        // DFS
        // 规定一个方向进行搜索
    // （1）访问顶点v；
    // （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
    // （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　
    // 当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).
    
        // DFS 对比: DFS进行单条遍历直到走不通再回溯到另外一条，而BFS是将所有可能的都加入队列进行同时搜索
        // DFS 递归思想 BFS 队列
        // 采用邻阶表
        class DfsNode{ 
            int val;//该边的值
            List<DfsNode> nextNodeList =new ArrayList<>();
            //
    
            public DfsNode() { 
            }
    
            public DfsNode(int val, List<DfsNode> nextNodeList) { 
                this.val = val;
                this.nextNodeList = nextNodeList;
            }
    
            public int getVal() { 
                return val;
            }
    
            public void setVal(int val) { 
                this.val = val;
            }
    
            public List<DfsNode> getNextNodeList() { 
                return nextNodeList;
            }
    
            public void setNextNodeList(List<DfsNode> nextNodeList) { 
                this.nextNodeList = nextNodeList;
            }
        }
    
        int step =1;
        static int[] visited1 =new int[100];// 如果值为对象可以使用map建立映射，或者hash函数
        static { 
            Arrays.fill(visited1,0);
        }
        void dfs(DfsNode node){ //目标边值
            System.out.println("第"+step+"步搜索");
            step++;
            visited1[node.getVal()]=1;//被访问
            if(node.getVal()==10){ 
                System.out.println("寻找到该边");
            }else if(node.getNextNodeList()==null){ //需要前驱？？,八皇后，棋盘控制
                //回溯
                 // 停止操作即可，即进入下一个
            }else { // 深搜
                    for(int i =0;i<node.getNextNodeList().size();i++){ 
                        if(visited1[node.getNextNodeList().get(i).getVal()]==0){ // 该边为被访问
                            dfs(node.getNextNodeList().get(i));
                        }
                    }
                 }
        }
    
    
    
        void test(){ 
            DfsNode node0= new DfsNode(0,null);
            DfsNode node1= new DfsNode(1,null);
            DfsNode node2= new DfsNode(2,null);
            DfsNode node3= new DfsNode(3,null);
            DfsNode node4= new DfsNode(4,null);
            DfsNode node10= new DfsNode(10,null);
    
    
            List<DfsNode> node0List = new ArrayList<>();
            node0List.add(node2);// 先搜索2
            node0List.add(node1);
            node0.setNextNodeList(node0List);
    
            List<DfsNode> node2List = new ArrayList<>();
            node2List.add(node3);
            node2List.add(node10);
            node2.setNextNodeList(node2List);
    
            dfs(node0);
    
    
    
        }
    
    
    
        public static void main(String[]args){ 
            Graph g= new Graph();
            g.test();
        }
    }