迷宫算法

数据结构迷宫算法

---

一.题目叙述

从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达一个新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。这里可以用一个栈来实现，每走一步，将该位置压入栈中，若该点无路可走，则出栈返回上一位置。

二.大致题意

用maze[m+2][n+2]来表示迷宫，maze[i][j]=0或1,等于零时通路，等1时不通路，想象迷宫四个面是墙壁，不通设为1，则可大概构造一个迷宫，如构在这里插入代码片造一个八行十列的迷宫，设定入口（1，1），出口（6，1），问有没有路径可以出去，如果有的话将路径表示出来。
int[][] maze = {{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,1,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,1,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}};

三.解题思路

一个人在（1，1）处进入迷宫，那么他在迷宫中有八个方向可以去尝试，分别是“左，右，前，后，左前，左后，右前，右后”，我们之前设定的迷宫四面都是墙则可保证迷宫内每一处都有八个方向可以试探，
他要去的的点对于当前所在点横纵坐标的变化量，可以用一个8*2的二维数组move表述，在move数组中，x表示横坐标的增量，y表示纵坐标的增量。
x y
0，1
1，1
1，0
1 , -1
0 , -1
-1 ,-1
-1 , 0
-1 , 1
同时为了防止重复的到达一个位置进入死循环，到了一点后maze[i][j]=-1,与未到达的点区分开来

四.测试结果

四.源码

package com.stack;
import java.util.Stack;            //导入java.util.Stack类
class Step{
    int x,y,d;
    public Step(int x,int y,int d) {       //栈中所存放的元素应该包含所到达的每点的坐标以及从该点沿哪个方向走的
        this.x = x;    //横坐标
        this.y = y;    //纵坐标
        this.d = d;    //方向
    }
}

public class migon {

    public static void main(String[] args) {
        // 迷宫定义
        int[][] maze = {                          //1表示不通，0表示通，迷宫四周设为1，真正的（1,1)位于第二行第二个
                {1,1,1,1,1,1,1,1,1,1},            //设入口(1,1),出口(6,1)
                {1,0,1,1,1,0,1,1,1,1},
                {1,1,0,1,0,1,1,1,1,1},
                {1,0,1,0,0,0,0,0,1,1},
                {1,0,1,1,1,0,1,1,1,1},
                {1,1,0,0,1,1,0,0,0,1},
                {1,0,1,1,0,0,1,1,0,1},
                {1,1,1,1,1,1,1,1,1,1}
        };
        int[][] move = {                         //二维数组move表示移动方向，x表示横坐标增量，y表示纵坐标增量
                {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}       //迷宫内点有八个试探方向
        };
        Stack<Step> s = new Stack<Step>();            //实例化对象
        int a = path(maze, move, s);
        while(!s.isEmpty()){       //假如s不为空（还有元素），继续循环
            Step step = s.pop();     
            System.out.println(step.x+":"+step.y);
        }
    }
    public static int path(int[][] maze,int[][] move,Stack<Step> s){
        Step temp = new Step(1,1,-1); //起点
        s.push(temp);
        while(!s.isEmpty()){
            s.pop();    //如果路走不通就出栈
            if(!s.isEmpty()){
                temp = s.peek();   //将栈顶元素设置为当前位置
            }
            int x = temp.x;
            int y = temp.y;
            int d = temp.d+1;
            while(d<8){          //小于八的试探方向条件下
                int i = x + move[d][0];
                int j = y + move[d][1];
                if(maze[i][j] == 0){    //该点可达
                    temp = new Step(i,j,d); //到达新点
                    s.push(temp);       //出栈
                    x = i;
                    y = j;
                    maze[x][y] = -1;  //到达新点，标志已经到达，区别于未到达的点，防止重复到达某点而发生死循环
                    if(x == 6 && y == 1){
                        return 1;  //到达出口，迷宫有路，返回1
                    }else{
                        d = 0;  //重新初始化方向
                    }
                }else{
                    d++; //改变方向
                }
            }
        }
        return 0;
    }

}