@yexiaoqi 2022-05-20T08:41:43.000000Z 字数 1575 阅读 401

# HJ43. 迷宫问题

int maze[5][5] = {0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0};

1. public class Main {
2. public static boolean isEnd = false;
3. public static void main(String[] args){
4. Scanner in = new Scanner(System.in);
5. while(in.hasNext()){
6. int n = in.nextInt();
7. int m = in.nextInt();
8. int[][] map = new int[n][m];
9. for(int i=0; i<n; i++){
10. for(int j=0; j<m; j++){
11. map[i][j] = in.nextInt();
12. }
13. }
14. //路径存储的集合
15. List<Pos> path = new ArrayList<>();
16. isEnd = false;
17. backtrack(map, path,0, 0);
18. for(Pos p : path){
19. System.out.println(p.toString());
20. }
21. }
22. }
23. private static void backtrack(int[][] map, List<Pos> path, int x, int y) {
24. //越界了
25. if (x<0 || x>map.length-1 || y<0 || y>map[0].length-1) return;
26. //撞墙了 或者 到终点了
27. if (map[x][y] == 1 || isEnd) return;
28. //结束条件
29. if(x==map.length-1 && y==map[0].length-1) {
30. path.add(new Pos(x, y));//添加终点
31. isEnd = true;
32. return;
33. };
34. map[x][y] = 1;//标记走过的点，以防倒着走回去
35. path.add(new Pos(x, y));
36. //以 x,y 为中心，向上下左右搜索
37. backtrack(map, path, x-1, y);
38. backtrack(map, path, x+1, y);
39. backtrack(map, path, x, y-1);
40. backtrack(map, path, x, y+1);
41. map[x][y] = 0;//回溯，恢复到之前的点的状态
42. if (!isEnd)//如果已经到右下角了，路径就不移除了，后面还要打印
43. path.remove(path.size()-1);//回溯，移除路径最后一个点
44. }
45. public static class Pos{
46. int x;
47. int y;
48. public Pos(int x, int y){
49. this.x = x;
50. this.y = y;
51. }
52. public String toString() {
53. return "("+x+","+y+")";
54. }
55. }
56. }

• 私有
• 公开
• 删除