编程题：地牢逃脱

旧城等待， 2022-05-24 12:22 102阅读 0赞

## 题目描述 ##

给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x 0  , y 0  ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。

## 输入描述: ##

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）

## 输出描述: ##

输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。

示例1

## 输入 ##

复制

3 3
    ...
    ...
    ...
    0 1
    4
    1 0
    0 1
    -1 0
    0 -1

## 输出 ##

复制

### 解题思路： ###

最差情况：

1.若是所有的点都可以到达，最差的情况刚好需要走的最大步数到达的那个位置是出口

2.若是有的位置到达不了，而刚好那个位置又是出口，无疑这就是最差情况，返回-1

3.有墙堵在面前其实是可以跳的。。。。。。。。厉害了（我在想如果可以跳个三个位置的话，为什么不能小用点力少跳点。。。）

#### 理解了最差情况题目就比较简单了，使用广度优先搜索 ####

### 代码： ###

####  ####

package net.stxy.one.controller;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    /**
     * Created by ASUS on 2018/5/27
     *
     * @Authod Grey Wolf
     */
    public class Test1 {
        public static void main(String[] args) {
            Test1 test1=new Test1();
            test1.sys();
        }
    
        private void sys() {
            Scanner scanner=new Scanner(System.in);
            int i;
            while (scanner.hasNext()){
                int n=scanner.nextInt();
                int m=scanner.nextInt();
                char[][]map=new char[n][m];
                for (i=0;i<n;i++){
                    String s=scanner.next();
                    map[i]=s.toCharArray();
                }
                //初始出发坐标
                int startX=scanner.nextInt();
                int startY=scanner.nextInt();
                int k=scanner.nextInt();
                int [][]move=new int[k][2];
                for(i=0;i<k;i++){
                    move[i][0]=scanner.nextInt();
                    move[i][1]=scanner.nextInt();
                }
                int maxStep=getResult(n,m,map,startX,startY,k,move);
                System.out.println("step:"+maxStep);
            }
        }
    
        private int getResult(int n, int m, char[][] map, int startX, int startY, int k, int[][] move) {
            //访问标记
            int [][]dis=new int[n][m];
            //引入队列是为了遍历没有出路为止，广度遍历一般都需要队列
            Queue<Integer>queueX=new LinkedList<Integer>();
            Queue<Integer>queueY=new LinkedList<Integer>();
            //添加起始位置
            queueX.add(startX);
            queueY.add(startY);
            //1表示已访问
            dis[startX][startY]=1;
            int i,j;
            while (!queueX.isEmpty()&&!queueY.isEmpty()){
                startX=queueX.remove();
                startY=queueY.remove();
                for (i=0;i<k;i++){
                    //保证不出界
                    if(startX+move[i][0]>=0&&startX+move[i][0]<n&&startY+move[i][1]>=0&&startY+move[i][1]<m){
                        //即将的路径还没访问的情况下
                        if (dis[startX+move[i][0]][startY+move[i][1]]==0){
                            //可以通行
                            if(map[startX+move[i][0]][startY+move[i][1]]=='.'){
                                //把该路径加入队列
                                queueX.add(startX+move[i][0]);
                                queueY.add(startY+move[i][1]);
                                //标记为已访问
                                dis[startX+move[i][0]][startY+move[i][1]]=dis[startX][startY]+1;
                            }else {
                                dis[startX+move[i][0]][startY+move[i][1]]=-1;
                            }
                        }
                    }
                }
            }//while end
            int maxStep=Integer.MIN_VALUE;
            int hasRoad=1;
            for (i=0;i<n;i++){
                for (j=0;j<m;j++){
                    if(dis[i][j]==0&&map[i][j]=='.'){
                        //存在没有被访问的“.”,说明路径不能遍历完全，有些出口到不了。
                        hasRoad=0;
                    }
                    maxStep=Math.max(dis[i][j],maxStep);
                }
            }
            if(hasRoad==0){
                return -1;
            }else{
                //因为起始步的dis值为1，这里要减去1
                return maxStep-1;
            }
    
        }
    
    }

### 代码效果： ###

3 3  
...  
...  
...  
0 1  
4  
1 0  
0 1  
\-1 0  
0 -1  
step:3  
  
我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。