题解 | 地下迷宫

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[][] G;
    static int[][] HP;
    static int n,m,P;
    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void bfs(int x, int y, int t, ArrayList<ArrayList<Integer>> road){
        if(x<0 || x>=n || y<0 || y>=m) return; //越界
        if(G[x][y]==0 && !(x==0&&y==0)) return; //障碍
        if(t<=HP[x][y]) return; //现在的走法还没有历史走法剩余体力多
        if(t<0) return; //体力透支

        //没到终点
        HP[x][y] = t;
        ArrayList<ArrayList<Integer>> newRoad = new ArrayList<>(road);
        newRoad.add(new ArrayList<>(Arrays.asList(x, y)));
        
        //走到终点
        if(x==0 && y==m-1){
            res = newRoad;
            HP[0][m-1] = t;
            return;
        }
        
        bfs(x,y+1,t-1,newRoad);
        bfs(x+1,y,t,newRoad);
        bfs(x-1,y,t-3,newRoad);
        bfs(x,y-1,t-1,newRoad);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        P = sc.nextInt();
        G = new int[n][m];
        HP = new int[n][m];
        // HP[0][0] = P;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) G[i][j] = sc.nextInt();
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                HP[i][j] = Integer.MIN_VALUE;
        // System.out.println(Arrays.deepToString(G)); [[1, 0, 0, 1], [1, 1, 0, 1], [0, 1, 1, 1], [0, 0, 1, 1]]
        bfs(0,0,P,new ArrayList<>());
        // System.out.println(Arrays.deepToString(G));
        // System.out.println(Arrays.deepToString(HP));

        //输出答案
        if(res.isEmpty()) System.out.println("Can not escape!");
        // else System.out.println(res);
        else{
            StringBuffer sb = new StringBuffer();
            for(int i=0;i<res.size();i++){
                sb.append(res.get(i).toString());
                if(i<res.size()-1) sb.append(",");
            }
            System.out.println(sb.toString().replace(" ",""));
        }
    }
}

java选手需要注意的点：

1.和python不同，bfs的时候注意创建入参的拷贝，不能像python一样自动就能够构建新对象。并且，只需要创建1份拷贝而不是4份，因为每次递归调用bfs的时候，都会执行创建新的newRoad对象，不会影响到入参road

2.ArrayList输出时会多带一个空格，要去除空格需要用到String.replace（）方法，replace(" ","")才能够去除空格

3.ArryaList输出自带[]，需要手动去除掉