使用栈寻找迷宫通路

骑猪看日落 2022-03-22 11:41 129阅读 0赞

# 问题描述: #

给定一个n\*n的迷宫矩阵,障碍物记为1,无障碍记为0

> int\[\]\[\] map = new int\[\]\[\]\{  
> \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\},  
> \{1, **0, 0**, 1, 1, 1, 1, 1, 1, 1, 1, 1\},  
> \{1, 1, **0, 0, 0**, 1, 1, 1, 1, 1, 1, 1\},  
> \{1, 1, 1, **0, 0**, 1, 1, 1, 1, 1, 1, 1\},  
> \{1, 1, 1, 1, **0, 0**, 1, 1, 1, 1, 1, 1\},  
> \{1, 1, 1, 1, 1, **0, 0, 0**, 1, 1, 1, 1\},  
> \{1, 1, 1, 1, 1, 1, **0**, 1, 1, 1, 1, 1\},  
> \{1, 1, 1, 1, 1, 1, **0, 0,** 1, 1, 1, 1\},  
> \{1, 1, 1, 1, 1, 1, 1, **0, 0, 0**, 1, 1\},  
> \{1, 1, 1, 1, 1, 1, 1, 1, 1, **0**, 1, 1\},  
> \{1, 1, 1, 1, 1, 1, 1, 1, 1, **0, 0**, 1\},  
> \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}\};

**要求:**

1.  使用栈实现
2.  非递归算法实现
3.  递归算法实现

## 思路: ##

### 1.非递归思路: ###

1.  将起点入栈
2.  进入循环 (**主循环**),循环条件是 **栈不空** 或者**栈顶元素坐标为终点坐标**
3.  循环中依次 **对栈顶元素的 右,下,左,上**(内循环)四个方向判断是否为0,一旦出现一个为0,压入该节点,该节点标记为2(已访问); 内部循环进行的条件是,不为0的次数<4,如果等于4,说明栈顶元素的四个方向都是堵住的,弹出栈顶元素,结束内层循环
4.  主循环结束后,通过判断栈是否为空,可以判断是否寻找到通路

#### java 代码实现: ####

import java.util.Stack;
    
    /** * @author wangwei * @date 2019/1/27 20:42 * @classDescription 迷宫寻找出口路径: * 1,使用栈记录正确路径,同时也是方便回退 */
    class mapNode { 
        int x;
        int y;
    
        public mapNode(int x, int y) { 
            this.x = x;
            this.y = y;
        }
    
        public int getX() { 
            return x;
        }
    
        public void setX(int x) { 
            this.x = x;
        }
    
        public int getY() { 
            return y;
        }
    
        public void setY(int y) { 
            this.y = y;
        }
    
        @Override
        public String toString() { 
            return "mapNode{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
    
    public class MazeStack { 
        //使用 10*10 的矩阵 12*12 最外层是墙
        // 1 表示墙
        // 0 表示可走
        static final int N_WIDTH = 12;
        static final int N_HEIGHT = 12;
        int[][] map = new int[][]{ 
                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                { 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                { 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1},
                { 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1},
                { 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
                { 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1},
                { 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
                { 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1},
                { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    // boolean[][] reachable = new boolean[N_WIDTH][N_HEIGHT];
    
    // //初始化reachable 数组,标记是否可以到达,辅助数组,能通过为true,已访问,不能通过为false,此代码展示未使用
    // public void init() { 
    // for (int i = 0; i < N_WIDTH; i++) { 
    // for (int j = 0; j < N_HEIGHT; j++) { 
    // boolean reach = map[i][j] == 0;
    // reachable[i][j] = reach;
    // }
    // }
    // }
      /** * @author wangwei * @date 2019/1/28 10:44 * @methodDescription 非递归方式实现 * * 从起点开始:顺时针方向扫描元素,如果可达,标记为已经扫描,压栈,以该位置继续顺时针方向扫 如果不可达:更改扫描方向 如果所有方向都已经扫描,不可达, ,退栈 保存当前节点到栈中,继续探测该节点周围节点 */
        public boolean searchWay(Stack<mapNode> way,int currX, int currY, int outX, int outY) { 
    
         
            way.push(new mapNode(currX, currY));
            map[currX][currY] = 2;
            while (!way.isEmpty()) { 
    
                mapNode currNode = way.peek();//取栈顶元素作为当次扫描的中间位置
                if (outX == currNode.getX() && outY == currNode.getY()) { 
                    System.out.println("找到出路");
                    return true;
                }
                // 下一个节点:如果是 0 ,则入栈
                currX = currNode.getX();
                currY = currNode.getY();
                int failed = 0;
                if (map[currX][currY + 1] == 0) { 
                    way.push(new mapNode(currX, currY + 1));
                    map[currX][currY + 1] = 2;//标记为已经到过
                } else { 
                    failed++;
                }
                if (map[currX + 1][currY] == 0) { 
                    way.push(new mapNode(currX + 1, currY));
                    map[currX + 1][currY] = 2;//标记为已经到过
                } else { 
                    failed++;
                }
                if (map[currX][currY - 1] == 0) { 
                    way.push(new mapNode(currX, currY + 1));
                    map[currX][currY - 1] = 2;//标记为已经到过
                } else { 
                    failed++;
                }
                if (map[currX - 1][currY] == 0) { 
                    way.push(new mapNode(currX - 1, currY));
                    map[currX - 1][currY] = 2;//标记为已经到过
                } else { 
                    failed++;
                }
                //四个方向全部失败,说明栈顶元素周围被堵死,或者都被访问过
                if (failed > 3) { 
                    way.pop();
                }
    
            }
            return false;
    
        }
        public static void main(String[] args) { 
            Stack<mapNode> throughWay = new Stack<>();
    
            MazeStack mazeStack = new MazeStack();
    
            mazeStack.searchWay(throughWay,1,1,10,10);
            System.out.println("找到的通路:");
            while (!throughWay.empty()) { 
                System.out.println(throughWay.pop());
            }
    
        }

#### 测试结果: ####

> 找到出路  
> 找到的通路:  
> mapNode\{x=10, y=10\}  
> mapNode\{x=10, y=9\}  
> mapNode\{x=9, y=9\}  
> mapNode\{x=8, y=9\}  
> mapNode\{x=8, y=8\}  
> mapNode\{x=8, y=7\}  
> mapNode\{x=7, y=7\}  
> mapNode\{x=7, y=6\}  
> mapNode\{x=6, y=6\}  
> mapNode\{x=5, y=7\}  
> mapNode\{x=5, y=6\}  
> mapNode\{x=5, y=5\}  
> mapNode\{x=4, y=5\}  
> mapNode\{x=4, y=4\}  
> mapNode\{x=3, y=4\}  
> mapNode\{x=3, y=3\}  
> mapNode\{x=2, y=4\}  
> mapNode\{x=2, y=3\}  
> mapNode\{x=2, y=2\}  
> mapNode\{x=1, y=2\}  
> mapNode\{x=1, y=1\}

Process finished with exit code 0

### 2.递归思路, ###

首先将起点入栈,并且将数组中该点位置做上标记,比如改值为2(或者另起一个辅助数组)  
2,对栈顶元素的四个方向节点进行扫描(假定是顺时针)  
2.1 访问右节点  
2.1.1 如果右节点值为0,将其标记为 2(已访问),压入右节点,递归调用  
2.2 如果右节点!=0,访问下节点,  
2.2.1 下节点如果为0,标记为2(已访问),压入该节点,递归调用  
2.3 如果下节点!=0,访问左节点,  
2.3.1 如果左节点为0,标记为2,入栈,压入该节点,递归调用  
2.4 如果 左节点!=0,访问上节点,  
2.41如果上节点为0,标记为2,入栈,递归调用  
2.42 否则(说明四个方向都不为0),弹出栈顶元素,递归调用  
\*\*退出递归条件:\*\*这点非常重要,不然会出现StackOverFlow 异常,整的一脸懵逼  
1,栈为空,表示没有通路  
2,栈顶元素坐标与出口坐标相同,表示找到通路

#### java 代码实现: ####

//使用递归的方式查找出路,
        public boolean findWay(Stack<mapNode> way,  int outX, int outY) { 
            int curX = way.peek().getX();
            int curY = way.peek().getY();
            //成功找到出口
            if (curX == outX && curY == outY) { 
                return true;
            }
            //四周加上了一堵墙,这行判断就可以去掉了
    // if (curX < 0 || curX > N_WIDTH - 1 || curY < 0 || curY > N_HEIGHT - 1) { 
    // return false;
    // }
            //栈中元素一定是可以到达的,接下来是检测其周围元素
            //右,下,左,上
            if (map[curX][curY + 1] == 0) { 
                map[curX][curY + 1]=2;//标记为已访问
              way.push(new mapNode(curX,curY+1));
              return  findWay(way,outX,outY);
            }
            if (map[curX+1][curY ] == 0) { 
                map[curX+1][curY]=2;
                way.push(new mapNode(curX+1,curY));
                return  findWay(way,outX,outY);
            }
            if (map[curX][curY -1] == 0) { 
                map[curX][curY-1]=2;
                way.push(new mapNode(curX,curY-1));
                return  findWay(way,outX,outY);
            }
            if (map[curX-1][curY ] == 0) { 
                way.push(new mapNode(curX-1,curY));
                return  findWay(way,outX,outY);
            }
            //四个方向都不可通过,弹出栈顶元素,
             way.pop();
            return findWay(way,outX,outY);
        }

#### 测试代码: ####

public static void main(String[] args) { 
            Stack<mapNode> throughWay = new Stack<>();
            MazeStack mazeStack = new MazeStack();
             throughWay.push(new mapNode(1,1));//压入起点
             mazeStack.findWay(throughWay,  10, 10);
            System.out.println("找到的通路:");
            while (!throughWay.empty()) { 
                System.out.println(throughWay.pop());
            }
    
        }

测试效果:

> 找到的通路:  
> mapNode\{x=10, y=10\}  
> mapNode\{x=10, y=9\}  
> mapNode\{x=9, y=9\}  
> mapNode\{x=8, y=9\}  
> mapNode\{x=8, y=8\}  
> mapNode\{x=8, y=7\}  
> mapNode\{x=7, y=7\}  
> mapNode\{x=7, y=6\}  
> mapNode\{x=6, y=6\}  
> mapNode\{x=5, y=6\}  
> mapNode\{x=5, y=5\}  
> mapNode\{x=4, y=5\}  
> mapNode\{x=4, y=4\}  
> mapNode\{x=3, y=4\}  
> mapNode\{x=2, y=4\}  
> mapNode\{x=2, y=3\}  
> mapNode\{x=2, y=2\}  
> mapNode\{x=1, y=2\}  
> mapNode\{x=1, y=1\}

## 总结: ##

1.  使用了栈保存**当前可能**的一个在通路上的节点(值为0,即入栈,并且标记已访问,至于它**最终能否保留在栈中,还得看四周节点是否为0**)
2.  如果栈顶元素的四周都是不能到达的(或者已经**标记过已访问**),那么栈顶元素是**不能保留在 入口=>出口** 的路径上,需要将其弹出
3.  如果栈为空,表明即使是起点放到栈中,起点也被墙隔离了,肯定是死路
4.  递归算法,一定要特别注意递归结束条件!!!