牛客地下迷宫

墨蓝 2023-07-25 15:29 15阅读 0赞

小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值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\]

//思路分析：采用递归的方法分别像上下左右四个方向找出口，找到出口以后与上一条比较是否为更省能量的一条路径，
    // 如果是，就更新路径，如果不是，就继续递归。
    
    import java.util.Scanner;
    
    public class MazeDungeon {
        public static String road = "";
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int p =sc.nextInt();
            int[][] maze = new int[n][m];
            boolean[][] realroad = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j =0; j < m; j++) {
                    maze[i][j] = sc.nextInt();
                }
            }
            Solution(maze,realroad,0,0,"",p);
            System.out.println(road);
        }
    
        //road是最后唯一的路径
        //tryroad 是尝试的路径，在递归中不断改变最后移动到出口
        public static void Solution(int[][] maze,boolean[][] realroad,int i,
                                    int j, String tryroad,int p) {
            if (i == 0 && j == maze[0].length-1 && maze[i][j] == 1) {
                if (p >= 0) {
                    road = tryroad + "[" + i + ","+ j + "]";
                 } else {
                    road = "Can not escape!";
                }
                return;
            }
            if (i >= 0 && j >= 0 && i < maze.length && j < maze[0].length && maze[i][j] == 1 && !realroad[i][j]) {
                realroad[i][j] = true;
                tryroad += "[" + i +"," + j + "]";
                Solution(maze,realroad,i,j+1,tryroad,p-1); //向右
                Solution(maze,realroad,i+1,j,tryroad,p-1); //向下
                Solution(maze,realroad,i,j-1,tryroad,p-1); //向左
                Solution(maze,realroad,i-1,j,tryroad,p-1); //向前
    
            }
        }
    }

![在这里插入图片描述][20200415184953138.png]

[20200415184953138.png]: /images/20230528/980b159972d04e08ba32eabbbbd6b271.png