编程题：地牢逃脱

题目描述

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

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x₀, y₀，表示牛牛的出发位置（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

输出

复制 3

解题思路：

最差情况：

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 141 00 1-1 00 -1step:3我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。