题目描述
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
输入描述:
输入包括n+1行:
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者1,以空格分隔
输出描述:
如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一
示例1
输入
4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1
输出
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
1 import java.util.Iterator; 2 import java.util.LinkedList; 3 import java.util.Scanner; 4 /** 5 * 地下迷宫 6 * 深度优先遍历 7 * @author Dell 8 * 9 */ 10 public class Main { 11 static public int n,m,maxRemainEnergy = 0; 12 static public int map[][]; 13 static public boolean flag = false; 14 static String path = ""; 15 static LinkedList<String> linkedList = new LinkedList(); 16 17 static public void runMap(int x, int y, int energy) { 18 if (energy < 0 || x < 0 || y < 0 || x >= n || y >= m || map[x][y] != 1) { 19 return; 20 } else { 21 linkedList.offer("[" + x + "," + y + "]"); 22 map[x][y] = 0; // 堵住回去的路 23 if (x == 0 && y == m - 1) { 24 if (energy >= maxRemainEnergy) { // 如果剩余体力大于目前最大剩余就替换路径,得到最省体力的路径 25 maxRemainEnergy = energy; 26 updatePath(); 27 } 28 map[x][y] = 1; // 释放回去的路 29 linkedList.removeLast(); // 继续查找 有没有·更优的方法 30 flag = true; 31 return; 32 } 33 runMap(x, y + 1, energy - 1); 34 runMap(x + 1, y, energy); 35 runMap(x - 1, y, energy - 3); 36 runMap(x, y - 1, energy - 1); 37 map[x][y] = 1; 38 linkedList.removeLast(); 39 } 40 } 41 static public void updatePath() { 42 StringBuilder sb = new StringBuilder(); 43 Iterator<String> iterator = linkedList.iterator(); 44 while(iterator.hasNext()) { 45 sb.append(iterator.next()+","); 46 } 47 if (sb.length()>0) { 48 sb.deleteCharAt(sb.length()-1);// 除去最后多的 , 49 path = sb.toString(); 50 } 51 } 52 public static void main(String[] args) { 53 // 输入 54 Scanner sc = new Scanner(System.in); 55 n = sc.nextInt(); 56 m = sc.nextInt(); 57 int P = sc.nextInt(); 58 map = new int[n][m]; 59 for (int i = 0; i < n; i++) { 60 for (int j = 0; j < m; j++) { 61 map[i][j] = sc.nextInt(); 62 } 63 } 64 // 处理 65 runMap(0, 0, P); 66 // 输出 67 if (!flag) { 68 System.out.println("Can not escape!"); 69 }else { 70 System.out.println(path); 71 } 72 } 73 }