蓝桥杯27-学霸作业

青旅半醒 2023-06-17 11:52 13阅读 0赞

--------------------

title: 蓝桥杯27-学霸作业  
date: 2019-11-28 19:11:20  
categories:

*  蓝桥杯  
    tags:
 *  蓝桥杯

--------------------

# 蓝桥杯27-学霸作业 #

*  题目描述：
    
    问题描述  
    　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。  
    输入格式  
    　　第一行两个整数n， m，为迷宫的长宽。  
    　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。  
    输出格式  
    　　第一行一个数为需要的最少步数K。  
    　　第二行K个字符，每个字符∈\{U,D,L,R\},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。  
    样例输入  
    Input Sample 1:  
    3 3  
    001  
    100  
    110
    
    Input Sample 2:  
    3 3  
    000  
    000  
    000  
    样例输出  
    Output Sample 1:  
    4  
    RDRD
    
    Output Sample 2:  
    4  
    DDRR  
    数据规模和约定  
    　　有20%的数据满足：1<=n,m<=10  
    　　有50%的数据满足：1<=n,m<=50  
    　　有100%的数据满足：1<=n,m<=500
 *  问题理解：
    
    1.  首先我们需要理解一下，这是一个寻找最短路径问题，所以我们可以使用广度优先搜索(bfs),bfs可以理解为一层一层的搜索，比如这样子的树结构：
        
        ![format_png][]
        
        从1开始搜，有2，3，4几个点，存起来，从2开始有5，6，存起来，搜3，有7，8，存起来，搜4，没有了；现在开始搜刚刚存的点，从5开始，没有，然后搜6.。。一直进行，直到找到
    2.  其次，我们需要处理好这个路径保存问题，因为我们需要返回去，这里我选择一种简单的办法，使用一个二维矩阵进行表示，二维矩阵的初始化为0，那么我们进行计算，每走过一条路径，这条路径点就重新赋值为1
    3.  最后，从终点倒退，这里我投机取巧，使用一个很简单的思路，就是遍历是下左上右,其实只要选好首先遍历点，怎么理解呢，就是对终点是往上往左往右往下的顺序if语句，这个语句能巧妙的保证我们是最短路
 *  代码实现：
    
    1.  我们自己封装好节点，节点的属性有横坐标，纵坐标，还有到这点路径的长度
        
            class node{ 
                public int x;
                public int y;
                public int d;
                public node(int x,int y,int d){ 
                    this.x = x;
                    this.y = y;
                    this.d = d;
                }
            
            }
    2.  使用bfs方法进行路径的宽度优先搜索
        
            Queue<node> queue = new LinkedList<>();
                    ((LinkedList<node>) queue).push(new node(0,0,1));
                    while (!queue.isEmpty()){ 
                        node front = ((LinkedList<node>) queue).pop();
                        for(int i=0;i<4;i++){ 
                            int x1 = front.x+direction[i][0];
                            int y1 = front.y+direction[i][1];
                            //这里条件判断是这样的，首先要求x1和y1在指定范围内
                            if(x1>=0&&y1>=0&&x1<m&&y1<n&&visit[x1][y1]==0&&trouble[x1][y1]!=1){ 
                                visit[x1][y1] = 1;
                                if(x1==m-1&y1==n-1)
                                    return front.d;
                                ((LinkedList<node>) queue).push(new node(x1,y1,front.d+1));
                            }
                        }
                    }
    3.  最后反向遍历得到想要的
        
            String string = "";
                    int i = m-1;
                    int j = n-1;
                    //这里的指定遍历是下左上右,其实只要选好首先遍历点
                    while((i>0||j>0)&&(j<n&&i<m)){ 
                        if(i>0&&visit[i-1][j]==1){ 
                            string+="D";
                            i--;
                        }else if(j>0&&visit[i][j-1]==1){ 
                            string +="R";
                            j--;
                        }else if(j<n&&visit[i][j+1]==1){ 
                            string +="U";
                            j++;
                        }else if(i<m&&visit[i+1][j]==1){ 
                            string +="L";
                            i++;
                        }
                    }
                    System.out.println(new StringBuilder(string).reverse());
    4.  总体代码：
        
            package lanqiao;
            //问题描述
            //        　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
            //        输入格式
            //        　　第一行两个整数n， m，为迷宫的长宽。
            //        　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
            //        输出格式
            //        　　第一行一个数为需要的最少步数K。
            //        　　第二行K个字符，每个字符∈{ U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
            //        样例输入
            //        Input Sample 1:
            //        3 3
            //        001
            //        100
            //        110
            //        Input Sample 2:
            //        3 3
            //        000
            //        000
            //        000
            //        样例输出
            //        Output Sample 1:
            //        4
            //        RDRD
            //        Output Sample 2:
            //        4
            //        DDRR
            //        数据规模和约定
            //        　　有20%的数据满足：1<=n,m<=10
            //        　　有50%的数据满足：1<=n,m<=50
            //        　　有100%的数据满足：1<=n,m<=500。
            import com.sun.jdi.event.StepEvent;
            
            import java.util.LinkedList;
            import java.util.Queue;
            import java.util.Scanner;
            //定义中间类，为了保存迷宫中走过的节点代表的d长度
            class node{ 
                public int x;
                public int y;
                public int d;
                public node(int x,int y,int d){ 
                    this.x = x;
                    this.y = y;
                    this.d = d;
                }
            
            }
            public class day1127 { 
                public static int[][] direction = new int[][]{ { 0,1},{ 0,-1},{ -1,0},{ 1,0}};//4个方向保存
                public  static int[][] visit;
                public static int[][] trouble;
                public static int m;
                public static int n;
                public  static void main(String[] args) { 
                    Scanner in  = new Scanner(System.in);
                    m = in.nextInt();
                    n = in.nextInt();
                    visit = new int[m][n];
                    trouble = new int[m][m];
                    in.nextLine();
                   // System.out.println(in.nextLine());//将换行读取
                    for(int i=0;i<m;i++){ 
                        String string = in.nextLine();
                        for(int j=0;j<n;j++){ 
                            trouble[i][j] = string.charAt(j)-'0';
                        }
                    }//读取为1的值，这些点需要绕过去
                    in.close();
                    int step = bfs();
                    findPath(step);
                }
                public static int bfs(){ 
                    visit[0][0]=1;
                    //初始化队列
                    //这里我们是这样选择的通过队列使用bfs
                    Queue<node> queue = new LinkedList<>();
                    ((LinkedList<node>) queue).push(new node(0,0,1));
                    while (!queue.isEmpty()){ 
                        node front = ((LinkedList<node>) queue).pop();
                        for(int i=0;i<4;i++){ 
                            int x1 = front.x+direction[i][0];
                            int y1 = front.y+direction[i][1];
                            //这里条件判断是这样的，首先要求x1和y1在指定范围内
                            if(x1>=0&&y1>=0&&x1<m&&y1<n&&visit[x1][y1]==0&&trouble[x1][y1]!=1){ 
                                visit[x1][y1] = 1;
                                if(x1==m-1&y1==n-1)
                                    return front.d;
                                ((LinkedList<node>) queue).push(new node(x1,y1,front.d+1));
                            }
                        }
                    }
                    return -1;
                }
                public static void findPath(int step){ 
                    String string = "";
                    int i = m-1;
                    int j = n-1;
                    //这里的指定遍历是下左上右,其实只要选好首先遍历点
                    while((i>0||j>0)&&(j<n&&i<m)){ 
                        if(i>0&&visit[i-1][j]==1){ 
                            string+="D";
                            i--;
                        }else if(j>0&&visit[i][j-1]==1){ 
                            string +="R";
                            j--;
                        }else if(j<n&&visit[i][j+1]==1){ 
                            string +="U";
                            j++;
                        }else if(i<m&&visit[i+1][j]==1){ 
                            string +="L";
                            i++;
                        }
                    }
                    System.out.println(new StringBuilder(string).reverse());
                }
            }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTMyOTY0Ny8yMDE4MDcvMTMyOTY0Ny0yMDE4MDczMTE3MDIwMDkxMy0xMTYxMzI1Mjc4LnBuZw?x-oss-process=image/format,png