华为OD机试真题 - 寻找最优的路测线路

暴力做法
    static int[][] DISTANCE = {{1,0},{-1,0},{0,1},{0,-1}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int H = scanner.nextInt();
        int W = scanner.nextInt();
        int[][] map = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                map[i][j] = scanner.nextInt();
            }
        }
        System.out.println(getMaxFlow(map));

    }

    public static int getMaxFlow(int[][] map) {
        if (map == null)
            return 0;
        boolean[][] visited = new boolean[map.length][map[0].length];

        Path path = new Path("", Integer.MAX_VALUE);
        List ans = new ArrayList<>();
        DFS(map, visited, path,0,0, ans);
        if (ans != null)
            return ans.get(0).maxFlow;
        else
            return 0;
    }

    public static void DFS(int[][] map, boolean[][] visited, Path path, int i, int j, List ans) {
        if (i < 0 || i >= map.length || j < 0 || j >= map[0].length)
            return;
        if (visited[i][j] == true)
            return;
        if (path.path.endsWith(map.length - 1 + "" + (map.length - 1) + "")) {
            ans.add(new Path(path.path, path.maxFlow));
            return;
        }
        visited[i][j] = true;
        path = new Path(path.path + i + j, Math.min(path.maxFlow, map[i][j]));
        for (int[] ints : DISTANCE) {
            DFS(map, visited, path, i + ints[0], j + ints[1], ans);
        }
        visited[i][j] = false;
    }

    static class Path {
        String path = null;
        int maxFlow = 0;
        public Path(String path, int maxFlow) {
            this.path = path;
            this.maxFlow = maxFlow;
        }
    }