java - 二元迷宫的技巧

Question

问题是一个二元迷宫，其中 1 是墙壁，0 是有效路径。您从左上角 (0,0) 开始，必须到达右下角(宽度 -1，高度 -1)。你必须找到从左上角到右下角的最短路径。扭曲的出现是因为你最多只能拆除一堵墙，这是让我感到困惑的部分。我当前的代码可以求解最短路径，而无需计算移除的墙。

这里有几个例子:[0,1,1,0], [0,0,0,1], [1,1,0,0], [1,1,1,0] 答案:7步(包括进出)

示例 2:[0,0,0,0,0],[0,1,1,1,0],[1,0,0,0,0],[0,1,1,1,1],[0 ,1,1,1,1],[0,0,0,0,0]答案:11(因为你可以打破[0][1]位置的墙壁，使路径更短)

就像我之前说的，我的代码会找到最短路径，但目前不会尝试移除墙壁以获得更短的路径，主要是因为我不明白如何做。我当时想，一次拆除一堵墙，然后不断地重新运行，看看是否产生了更短的路径，但这似乎是非常昂贵的操作，但它可能会完成工作。然而，我希望我能找到一种更清晰、更简单的方法来做到这一点。

import java.util.*;

    public class Maze { 
        public static void main(String [] args)
        {
            int[][] arr = new int[][] {
                {0,0,0,0,0},
                {1,1,1,1,0},
                {0,0,0,0,0},
                {0,1,1,1,1},
                {0,1,1,1,1},
                {0,0,0,0,0},
            };
            answer(arr);
        }
        public static int answer(int[][] maze) { 
            maze[maze.length-1][maze[0].length -1] = 9;
            Point p = getPathBFS(0,0,maze);
            int length = 1;

            while(p.getParent() != null) {
                p = p.getParent();
                length++;
            }
            System.out.println(length);
            return length;
        } 
         private static class Point {
            int x;
            int y;
            Point parent;

            public Point(int x, int y, Point parent) {
                this.x = x;
                this.y = y;
                this.parent = parent;
            }

            public Point getParent() {
                return this.parent;
            }
      }
      public static Queue<Point> q = new LinkedList<Point>();

        public static Point getPathBFS(int x, int y,int[][] arr) {

            q.add(new Point(x,y, null));

            while(!q.isEmpty()) {
                Point p = q.remove();

                if (arr[p.x][p.y] == 9) {
                    return p;
                }

                if(isFree(p.x+1,p.y,arr)) {
                    arr[p.x][p.y] = -1;
                    Point nextP = new Point(p.x+1,p.y, p);
                    q.add(nextP);
                }

                if(isFree(p.x-1,p.y,arr)) {
                    arr[p.x][p.y] = -1;
                    Point nextP = new Point(p.x-1,p.y, p);
                    q.add(nextP);
                }

                if(isFree(p.x,p.y+1,arr)) {
                    arr[p.x][p.y] = -1;
                    Point nextP = new Point(p.x,p.y+1, p);
                    q.add(nextP);
                }

                 if(isFree(p.x,p.y-1,arr)) {
                    arr[p.x][p.y] = -1;
                    Point nextP = new Point(p.x,p.y-1, p);
                    q.add(nextP);
                }

            }
            return null;
        }


        public static boolean isFree(int x, int y,int[][] arr) {
            if((x >= 0 && x < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) {
                return true;
            }
            return false;
        }
    }

Answer 1

需要注意的是，删除一个部分后穿过迷宫的最短路径由两条最短路径组成 - 从入口到删除的部分，然后从删除的部分到导出。

可以使用BFS计算迷宫中所有位置到起始位置的距离以及所有位置到结束位置的距离。

然后你可以找到一个位置，使得到入口和导出的距离之和最小。如果它是墙部分，那么它就是要移除的部分。否则，删除任何部分都是没有用的。

总体而言，该解决方案以线性时间运行。