地下迷宫 Java 题解

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // input n m and energy
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int energy = scanner.nextInt();
        // input nums
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }
        Main main = new Main();
        main.search(nums, n, m, energy);
    }

    private void search(int[][] nums, int n, int m, int energy) {
        ArrayList<Pair> result = new ArrayList<>();
        int resultEnergy = search(nums, n, m, energy, 0, 0, result);
        if(resultEnergy == -1){
            System.out.println("Can not escape!");
        }else{
            for (int i = 0; i < result.size(); i++) {
                System.out.print(result.get(i).toString());
                if (i != result.size() - 1) {
                    System.out.print(",");
                }
            }
        }
    }

    private int search(int[][] nums, int n, int m, int energy, int x, int y, ArrayList<Pair> result) {
        if (energy < 0 || x < 0 || x > n - 1 || y < 0 || y > m - 1 || nums[x][y] == 0) {
            return -1;
        } else {
            result.add(new Pair(x, y));
            if (x == 0 && y == m - 1) {
                return energy;
            } else {
                int leftMaxEnergy = -1;
                List<Pair> resultList = new ArrayList<>();
                nums[x][y] = 0;
                // up
                ArrayList<Pair> upResult = new ArrayList<>();
                int afterUp = search(nums, n, m, energy - 3, x - 1, y, upResult);
                if (afterUp > leftMaxEnergy) {
                    resultList = upResult;
                    leftMaxEnergy = afterUp;
                }
                // down
                ArrayList<Pair> downResult = new ArrayList<>();
                int afterDown = search(nums, n, m, energy, x + 1, y, downResult);
                if (afterDown > leftMaxEnergy) {
                    resultList = downResult;
                    leftMaxEnergy = afterDown;
                }
                // left
                ArrayList<Pair> leftResult = new ArrayList<>();
                int afterLeft = search(nums, n, m, energy - 1, x, y - 1, leftResult);
                if (afterLeft > leftMaxEnergy) {
                    resultList = leftResult;
                    leftMaxEnergy = afterLeft;
                }
                // right
                ArrayList<Pair> rightResult = new ArrayList<>();
                int afterRight = search(nums, n, m, energy - 1, x, y + 1, rightResult);
                if (afterRight > leftMaxEnergy) {
                    resultList = rightResult;
                    leftMaxEnergy = afterRight;
                }
                nums[x][y] = 1;
                result.addAll(resultList);
                return leftMaxEnergy;
            }
        }
    }
}

class Pair {
    private Integer key;
    private Integer value;

    public Pair(Integer key, Integer value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString() {
        return "[" + key + "," + value + "]";
    }
}