第一题动态规划解法，代码没优化，中间还有调试用的输出，额，有点长。大体思想，先求出（0,0）到各个点的最大剩余体力，然后从（0，m）开始倒推路径。 import java.util.Arrays; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int m = sc.nextInt(); int P = sc.nextInt(); int[][] nums = new int[n][m]; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ nums[i][j] = sc.nextInt(); } } if(n == 1){ System.out.println(P - m + 1); } if(m == 1){ System.out.println(P); } int[][] tili = new int[n][m]; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ tili[i][j] = -1; } } getSolution(nums, tili, P); dis(nums); System.out.println("tili"); dis(tili); findPath(nums, tili); } } public static void getSolution(int[][] nums, int[][] tili ,int P){ int n = nums.length; int m = nums[0].length; tili[0][0] = P; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(nums[i][j] == 0){ continue; } update(nums, tili, i, j); } } } public static void update(int[][] nums, int[][] tili, int i, int j){ if(tili[i][j] <= 0){ return; } if(i>0){ if(nums[i-1][j] == 1){ int p = tili[i][j] - 3; if(tili[i-1][j] < p){ tili[i-1][j] = p; update(nums, tili, i-1, j); } } } if(i<nums.length-1){ if(nums[i+1][j] == 1){ int p = tili[i][j]; if(tili[i+1][j] < p){ tili[i+1][j] = p; update(nums, tili, i+1, j); } } } if(j > 0){ if(nums[i][j-1] == 1){ int p = tili[i][j] - 1; if(tili[i][j-1] < p){ tili[i][j-1] = p; update(nums, tili, i, j-1); } } } if(j < nums[0].length-1) { if(nums[i][j+1] == 1){ int p = tili[i][j] - 1; if(tili[i][j+1] < p){ tili[i][j+1] = p; update(nums, tili, i, j+1); } } } } public static void findPath(int[][] nums, int[][] tili){ int n = tili.length; int m = tili[0].length; if(tili[0][m-1] == -1){ System.out.println("Can not escape!"); } Stack<String> stack = new Stack<String>(); String str = "[0," + (m-1) + "]"; stack.push(str); findnext(tili, 0, m-1, stack); while(!stack.isEmpty()){ System.out.print(stack.pop()); if(!stack.isEmpty()){ System.out.print(","); } } } public static void findnext(int[][] tili, int i, int j, Stack<String> s){ if(i==0 && j==0){ // String str = "[0,0]"; // s.push(str); return; } int up=0, down=0, left=0, right=0; int cur = tili[i][j]; if(i > 0){ up = tili[i-1][j]; if(up == cur){ String str = "[" + (i-1) + "," + j + "]"; s.push(str); findnext(tili, i-1, j, s); return; } } if(i < tili.length-1){ down = tili[i+1][j]; if(cur == down - 3){ String str = "[" + (i+1) + "," + j + "]"; s.push(str); findnext(tili, i+1, j, s); return; } } if(j >0){ left = tili[i][j-1]; if(cur == left - 1){ String str = "[" + (i) + "," + (j-1) + "]"; s.push(str); findnext(tili, i, j-1, s); return; } } if(j < tili[0].length-1){ right = tili[i][j+1]; if(cur == right - 1){ String str = "[" + (i) + "," + (j+1) + "]"; s.push(str); findnext(tili, i, j+1, s); return; } } } public static void dis(int[][] nums){ for(int i=0; i<nums.length; i++){ System.out.println(Arrays.toString(nums[i])); } } }