华为OD机试真题 - 智能驾驶

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = 0, n = 0;
        String line = in.nextLine();
        int[] mn = Arrays.stream(line.split(",")).mapToInt(Integer::parseInt).toArray();
        m = mn[0];
        n = mn[1];

        int[][] map = new int[m][n];
        int i = 0;
        while (in.hasNextLine()) {
            String line1 = in.nextLine();
            map[i] = Arrays.stream(line1.split(",")).mapToInt(Integer::parseInt).toArray();
            i++;
        }
        int space =  100;
        int banance = space;
        boolean[][] path = new boolean[m][n];
        for (int j = 0; j < path.length; j++) {
            Arrays.fill(path[j], false);
        }
        banance = dfs(map, banance, path, 0, 0);
        System.out.println(space - banance);
    }

    public static int dfs(int[][] map, int banance, boolean[][] path, int i, int j) {
        path[i][j] = true;
        if (map[i][j] == -1)
            banance = 100;
        else {
            banance = banance - map[i][j];
        }
        if (banance < 0)
            return banance;
        if (i == map.length - 1 &amp;&amp; j == map[i].length - 1)
            return banance;
        int down = Integer.MIN_VALUE;
        int left = Integer.MIN_VALUE;
        int up = Integer.MIN_VALUE;
        int right = Integer.MIN_VALUE;
        if (banance < 0)
            return banance;
        if (i + 1 < map.length &amp;&amp; path[i + 1][j] == false &amp;&amp; map[i + 1][j] != 0) {
            down = dfs(map, banance, path, i + 1, j);
            path[i + 1][j] = false;
            if (down < 0)
                down = Integer.MIN_VALUE;
        }
        if (i - 1 >= 0 &amp;&amp; path[i - 1][j] == false &amp;&amp; map[i - 1][j] != 0) {
            up = dfs(map, banance, path, i - 1, j);
            path[i - 1][j] = false;
            if (up < 0)
                up = Integer.MIN_VALUE;
        }
        if (j + 1 < map[i].length &amp;&amp; path[i][j + 1] == false &amp;&amp; map[i][j + 1] != 0) {
            right = dfs(map, banance, path, i, j + 1);
            path[i][j + 1] = false;
            if (right < 0)
                right = Integer.MIN_VALUE;
        }
        if (j - 1 >= 0 &amp;&amp; path[i][j - 1] == false &amp;&amp; map[i][j - 1] != 0) {
            left = dfs(map, banance, path, i, j - 1);
            path[i][j - 1] = false;
            if (left < 0)
                left = Integer.MIN_VALUE;
        }
        banance = Math.max(Math.max(down,up), Math.max(left,right));
        return banance;
    }