滴滴编程题两道AC

今天的编程题挺简单的~ 如果过的不多的话估计悬了、

走迷宫Java代码个人整理，供有需要的人参考。（可以求出所有路径和最优路径，以及最优路径下所耗的能量） import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; import java.util.Stack; class Pair{ public int x; public int y; public Pair(int x,int y) { this.x = x; this.y = y; } } public class Main { public static Stack<Pair> res = new Stack<>(); public static int[][] book;//用来标记改点是否走过，走过为1，没走为0 public static int[][] arr;//测试数组 public static int max = 0; public static Map<Integer, Stack<Pair>> map = new HashMap<>();//存放路径 public static void main(String ars[]) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int P = s.nextInt(); arr = new int[n][m];// 初始化数组 book = new int[n][m];// 初始化数组 for (int i = 0; i < n; i++)// 循环输入 for (int j = 0; j < m; j++) arr[i][j] = s.nextInt(); Stack<Pair> path = new Stack<>(); dfs(path,0,0,P); if (map.size() == 0) { System.out.println("Can not escape!"); }else { System.out.println("可以找到最优路径如下所示："); System.out.print("[0,0]"); Iterator<Pair> iter = map.get(max).iterator(); while (iter.hasNext()) { Pair pairTmp = iter.next(); System.out.print(",["+pairTmp.x+","+pairTmp.y+"]"); } System.out.println("\n最优路径所耗能量为："+(P-max)); } } public static void dfs(Stack<Pair> path, int x, int y, int P) { int n = arr.length; int m = arr[0].length; int next[][] = { {0,1}, {1,0}, {0,-1}, {-1,0} };//定义四个方向（分别是向右、向下、向左、向右） if (P <= 0 && x != 0 && y != m-1) { return; } //找到符合条件的路径 if (x == 0 && y == m-1) { if (P>=0) { Stack<Pair> pathTmp = new Stack<>(); Iterator<Pair> iter = path.iterator(); while (iter.hasNext()) { pathTmp.add(iter.next()); } map.put(P, pathTmp); } if (max < P) {//判断是否为最优路径 max = P; } return; } int tx,ty; //枚举四种走法 for (int k = 0; k <= 3; k++) { tx = x+next[k][0]; ty = y+next[k][1]; //判断是否越界 if (tx < 0 || tx >= n || ty < 0 || ty >= m) { continue; } if (arr[tx][ty] == 1 && book[tx][ty] == 0) { if (k == 0 || k==2) {//如果是水平方向走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P-1); path.pop(); book[tx][ty] = 0; } if (k==1) {//如果是向下走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P); path.pop(); book[tx][ty] = 0; } if (k==3) {//如果是向上走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P-3); path.pop(); book[tx][ty] = 0; } } } } }

太着急。wa了3发

大大大大大神啊！为什么这个运维也要写这样的题目啊

叼啊

恭喜恭喜

第一题我sb了 往上走一直搞成x+1了，只ac了30%

第一题 只过了 80% 晕了... 不知道怎么回事

不是要求消耗体力最少的路径吗？你代码里好像没体现最少啊？

第一题怎么保证得到的是剩余体力最多的路径？

第一题 ，x-1 的时候  p-3 ， 向下不消耗， 你刚好搞反了？

编程题AC是什么意思`````````

地下迷宫那道，你不判断哪条路径消耗体力最小么？

我考虑最小体力消耗搞得程序很复杂只ac了一部分，估计有bug但是没时间调试。如果用dfs全部ac只能说测试用例有问题。