/* * 时间: 2021-05-18 * 思路: DFS */ import java.util.*; public class Main { public static final int[] dir = {1, 0, -1, 0, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int row = sc.nextInt(); int col = sc.nextInt(); int[][] map = new int[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { map[i][j] = sc.nextInt(); } } Deque<String> result = new LinkedList<>(); Deque<String> output = new LinkedList<>(); dfs(map, 0, 0, result, output); while (!output.isEmpty()) { System.out.println(output.removeLast()); } } } public static void dfs(int[][] map, int i, int j, Deque<String> result, Deque<String> output) { if (i == map.length - 1 && j == map[0].length - 1) { if (output.isEmpty() || result.size() < output.size()) { output.clear(); output.addAll(result); // 将当前节点入栈 output.push("(" + i + "," + j + ")"); } return; } if (i < 0 || i >= map.length || j < 0 || j >= map[0].length) { return; } if (map[i][j] == 1) { return; } for (int m = 0; m < 4; m++) { map[i][j] = 1; result.push("(" + i + "," + j + ")"); dfs(map, i + dir[m], j + dir[m + 1], result, output); map[i][j] = 0; result.pop(); } } }