首页 > 代码库 > 青蛙走迷宫问题（体力值）
青蛙走迷宫问题（体力值）
题目：
青蛙走迷宫，1代表路通，0代表不通；起点是（0， 0），终点是（0，m - 1）;青蛙每次向上走需要消耗体力值为3，向下走不消耗体力值，平走消耗体力值1；根据给定值判断青蛙是否可以根据初始值到达终点，并求出消耗体力值最少的路径；
举例：
n = 4, m =4, p = 10(体力值)
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 package didi; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Scanner; 6 7 /** 8 * Created by leaves-pc on 2016/9/18. 9 * 青蛙问题 10 */ 11 public class Main { 12 public static int lastP = 0; //上次剩余的体力 13 public static void main(String[] args) throws Exception {
// 对输入做处理 14 Scanner scanner = new Scanner(System.in); 15 String line = ""; 16 if(scanner.hasNextLine()){ 17 line = scanner.nextLine(); 18 } 19 String[] str = line.split(" "); 20 if(str.length < 3) 21 throw new Exception(); 22 int n = Integer.valueOf(str[0]); 23 int m = Integer.valueOf(str[1]); 24 int P = Integer.valueOf(str[2]); 25 int[][] matrix = new int[n][m]; 26 int row = 0; 27 while(row < n && scanner.hasNextLine()){ 28 String[] s = scanner.nextLine().split(" "); 29 for(int i = 0; i < m; i++){ 30 matrix[row][i] = Integer.valueOf(s[i]); 31 } 32 row ++; 33 } 34 if(matrix[0][0] == 0 || matrix[0][m -1] == 0){ 35 System.out.println("Can not esape!"); 36 throw new Exception(); 37 }
// 输出一下矩阵 38 for(int i = 0; i < matrix.length; i++){ 39 for(int j = 0; j < matrix[0].length; j++){ 40 System.out.print(matrix[i][j] + " "); 41 } 42 System.out.println(); 43 } 44 List<List> res = new ArrayList<List>(); 45 List<List> list = new ArrayList<List>(); 46 List<Integer> temp = new ArrayList<Integer>(); 47 temp.add(0); 48 temp.add(0); 49 Count(matrix, 0, 0, P, res, list); 50 res.add(0, temp); // 初始位置（0， 0） 51 if(res.size() == 1) 52 System.out.println("Can not esape!"); 53 else 54 System.out.println(res.toString()); 55 56 } 57 public static void Count(int[][] matrix, int row, int col, int P, List<List> res, List<List> list){ 58 // System.out.println("row = " + row + ",col = " + col + ", P = " + P); 59 if(row == 0 && col == matrix[0].length - 1 && P >= 0){ 60 if(lastP < P){ // 这次剩的能量比较多，表明用的少，则更新路径 61 res.clear(); 62 res.addAll(list); 63 lastP = P; 64 } 65 return; 66 } 67 matrix[row][col] = 2; // 标记走过的 68 // 左走 69 if(col -1 >= 0 && matrix[row][col - 1] == 1 && P >= 1){ 70 List<Integer> temp = new ArrayList<Integer>(); 71 temp.add(row); 72 temp.add(col - 1); 73 list.add(temp); 74 Count(matrix, row, col - 1, P - 1, res, list); 75 } 76 // 上走 77 if(row - 1 >= 0 && matrix[row - 1][col] == 1 && P >= 3){ 78 List<Integer> temp = new ArrayList<Integer>(); 79 temp.add(row - 1); 80 temp.add(col); 81 list.add(temp); 82 Count(matrix, row - 1, col, P - 3, res, list); 83 } 84 // 右走 85 if(col + 1 < matrix[0].length && matrix[row][col + 1] == 1 && P >= 1){ 86 List<Integer> temp = new ArrayList<Integer>(); 87 temp.add(row); 88 temp.add(col + 1); 89 list.add(temp); 90 Count(matrix, row, col + 1, P - 1, res, list); 91 } 92 // 下走 93 if(row + 1 < matrix.length && matrix[row + 1][col] == 1){ 94 List<Integer> temp = new ArrayList<Integer>(); 95 temp.add(row + 1); 96 temp.add(col); 97 list.add(temp); 98 Count(matrix, row + 1, col, P, res, list); 99 }100 matrix[row][col] = 0;101 return ;102 103 }104 }
青蛙走迷宫问题（体力值）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。