暴力做法 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(&quot;&quot;, Integer.MAX_VALUE); List<Path> 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<Path> 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 + &quot;&quot; + (map.length - 1) + &quot;&quot;)) { 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; } }
查看5道真题和解析
投递华为等公司10个岗位