[关闭]
@yexiaoqi 2022-05-20T16:41:43.000000Z 字数 1575 阅读 495

HJ43. 迷宫问题

刷题


题目:定义一个二维数组 N*M ,如 5 × 5 数组下所示:

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表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围:2≤n,m≤10, 输入的内容只包含 0≤val≤1

输入描述:输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述:左上角到右下角的最短路径,格式如样例所示。
链接https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc


题目要求路线,考虑使用回溯法从左上角开始,向上下左右搜索。走到终点的时候,要不就把路径换一个地方存,要不就在后面回溯时根据结束标记判断一下,否则会把路径倒着一个个删掉,前功尽弃,/(ㄒoㄒ)/~~

  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. }

因为迷宫只有一条通道,不考虑最短路径的问题,否则需要在找到终点后比一下找出最短路径,参见网友解法

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注