带技巧的二进制迷宫

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来计算迷宫中所有位置到起始位置的距离和所有位置到结束位置的距离。

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

总的来说，这个解决方案在线性时间内运行。

Answer 2

您使用点 class 来表示玩家在迷宫中行走时的位置。没有墙规则，你只需要知道这个位置就可以决定他下一步可以做什么，所以你可以在所有可能位置的有向图上做 BFS 来找到路径。

有了墙规则，为了确定玩家下一步可以去哪里，你还必须知道他是否已经移除了一堵墙，所以玩家的完整状态不仅包括他的位置，还包括也是一个布尔值，指示墙是否已被移除。

然后你可以在这些扩展状态图上做BFS，找到最多移除一堵墙的最短路径。

由于您已经针对更简单的问题发布了您的实际代码，我将使用扩展状态（和一个 Set 来防止您访问相同状态两次，而不是修改 arr）来修复它：

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;
            State 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 State {
            int x;
            int y;
            boolean wallRemoved;

            State parent;

            public State(int x, int y, boolean wallRemoved, State parent) {
                this.x = x;
                this.y = y;
                this.wallRemoved = wallRemoved;
                this.parent = parent;
            }

            public State getParent() {
                return this.parent;
            }

            @Override
            public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + (wallRemoved ? 1231 : 1237);
                result = prime * result + x;
                result = prime * result + y;
                return result;
            }

            @Override
            public boolean equals(Object obj)  {
                if (this == obj)
                    return true;
                if (obj == null ||getClass() != obj.getClass())
                    return false;
                State other = (State) obj;
                if (wallRemoved != other.wallRemoved)
                    return false;
                if (x != other.x)
                    return false;
                if (y != other.y)
                    return false;
                return true;
            }

      }
      public static Queue<State> q = new LinkedList<>();
      public static HashSet<State> seen = new HashSet<>();

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

            q.add(new State(x,y,false, null));

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

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

                tryNext(p,p.x+1,p.y,arr);
                tryNext(p,p.x-1,p.y,arr);
                tryNext(p,p.x,p.y+1,arr);
                tryNext(p,p.x,p.y-1,arr);
            }
            return null;
        }

        public static void tryNext(State p, int x, int y, int[][]arr)  {
            if (x<0 || y<0 || x>=arr.length || y>=arr[x].length)
                return;
            State newState;
            if (arr[x][y] == 0 || arr[x][y]==9)  {
                newState = new State(x, y, p.wallRemoved, p);
            } else if (!p.wallRemoved) {
                newState = new State(x, y, true, p);
            } else {
                return;
            }
            if (seen.add(newState)) {
                q.add(newState);
            }
        }
    }

带技巧的二进制迷宫

Binary Maze with a Trick

java

breadth-first-search

maze

graph-layering