迷宫

用0表示可以走，1表示不可以走，从左上角走到右下角，能否找到一条路，如果找到，那么打印出来路径，用2表示走过的路径

如果找不到，那么图中尝试过的点置为 -1.

程序运行如下

输出如下

我的主要思路，首先用一个Maze类来表示迷宫上面的点，类中包含点的横纵坐标和点的值，用栈保存迷宫路径。从入口到出口，依次按照右 下 左 上判断四周是否是通路，如果是，将判断的点入栈，并将值置为2，如果四周都没有通路，那么当前点出栈，将值置为-1.
成功的条件是到达终点（即右下角的点），
失败的条件是:
       1.开始值不是0
       2.栈为空，表示没有路径。

实现的完整代码

Maze.java代码

public class Maze {
    private int x;
    private int y;
    private int value;

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

    public Maze(){

    }
    public Maze(int x,int y,int value){
        this.x = x;
        this.y = y;
        this.value = value;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
}

这里我没有用jdk提供的栈，自己学着写了一个简单的栈。

MyStack.java代码

public class MyStack {
    private final static int MAXSIZE = 10;
    private int top;
    private Maze[] mazes;

    public Maze getMazes(int i) {
        return mazes[i];
    }

    public void setMazes(Maze[] mazes) {
        this.mazes = mazes;
    }

    public int getTop() {
        return top;
    }

    public void setTop(int top) {
        this.top = top;
    }

    public MyStack(){
        top = -1;               //栈首下标
        mazes = new Maze[MAXSIZE];
    }
    //判栈空
    public boolean isEmpty(){
        if (top == -1){
            return true;
        }
        return false;
    }
    //栈溢出
    public boolean isFull(){
        if (top == MAXSIZE){
            return true;
        }
        return false;
    }
    //出栈
    public void pop(){
        top--;
    }
    //入栈
    public void push(Maze maze){
        top++;
        mazes[top] = maze;
    }

    public void printStack(){
        for (int i=0;i<=top;i++){
            System.out.println("("+mazes[i].getX()+","+mazes[i].getY()+")");
        }
    }
}

用MazeGame类表示一个迷宫，来保存所有的点，start()方法开始找入口，如果入口也就是（0，0）点不是0，那么没有路径，输出no way.否则表示可以进入，将（0，0）点入栈。road方法是主要实现代码，首先判栈空，如果栈是空的，那么表示没有可以走通的路径，用temp保存当前栈顶元素。startX，startY保存当前的横纵坐标。
       如果栈不空，判断当前迷宫点是否是终点，是终点游戏结束。不是终点开始判断是否有路径可以走，如果没有，该迷宫点出栈，用-1表示当前点已经走过。如果有，按照右 下 左 上的顺序依次判断，可以走，将该迷宫点入栈。

MazeGame.java代码

public class MazeGame {
    private Maze[][] mazes;
    public MazeGame(Maze[][] mazes){
        this.mazes = mazes;
    }

    public void start(){
        int startX = 0;
        int startY = 0;
        MyStack stack = new MyStack();
        mazeGamePrint();
        if (mazes[startX][startY].getValue() == 0){              // 入口是否为0
            stack.push(mazes[startX][startY]);
            mazes[startX][startY].setValue(2);                  //将以走过的路径置为2
        }else{
            System.out.println("no way");
            return ;
        }
        if(road(stack)){
            stack.printStack();
            mazeGamePrint();
        }else{
            System.out.println("no way！");
            mazeGamePrint();
        }
    }

    private boolean road(MyStack stack) {
        while(!stack.isEmpty()){
            int temp = stack.getTop();                              //栈顶元素
            int startX = stack.getMazes(temp).getX();
            int startY = stack.getMazes(temp).getY();
            if (startX == mazes.length-1 && startY == mazes[0].length-1){       //到达终点
                System.out.println("路径走过的坐标");
                return true;
            }else if (hasRoad(stack,startX,startY)){                                              //没有到达终点 且有路可走
                if(startY<mazes[0].length-1 && mazes[startX][startY+1].getValue() == 0){       //向右
                stack.push(mazes[startX][startY+1]);
                mazes[startX][startY+1].setValue(2);
                } else if (startX < mazes.length-1 && mazes[startX+1][startY].getValue() == 0){       //向下
                    stack.push(mazes[startX+1][startY]);
                    mazes[startX+1][startY].setValue(2);
                }else if (startY > 0 && mazes[startX][startY-1].getValue() == 0){       //向左
                    stack.push(mazes[startX][startY-1]);
                    mazes[startX][startY-1].setValue(2);
                } else if (startX > 0 && mazes[startX-1][startY].getValue() == 0){   //向上
                    stack.push(mazes[startX-1][startY]);
                    mazes[startX-1][startY].setValue(2);
                }
            }else{
                stack.pop();
                mazes[startX][startY].setValue(-1);
            }
        }
        return false;
    }

    private boolean hasRoad(MyStack stack,int startX,int startY) {
        if (startY<mazes[0].length-1 && mazes[startX][startY+1].getValue() == 0 ||
                startX < mazes.length-1 && mazes[startX+1][startY].getValue() == 0 ||
                startX > 0 && mazes[startX-1][startY].getValue() == 0 ||
                startY > 0 && mazes[startX][startY-1].getValue() == 0){
            return true;
        }
        return false;
    }

    public void mazeGamePrint(){
        for (int i=0;i<mazes.length;i++){
            for (int j=0;j<mazes[0].length;j++){
                System.out.print(mazes[i][j].getValue()+" ");
            }
            System.out.println();
        }
    }
}

测试代码Test.java

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入迷宫的行列数（m * n）:");
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        Maze[][] mazes = new Maze[m][n];
        System.out.println("请输入迷宫的路径");
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                mazes[i][j] = new Maze(i,j,scanner.nextInt());
            }
        }
        /*Maze[][] mazes = new Maze[][]{
                {new Maze(0,0,0),new Maze(0,1,1),new Maze(0,2,0)},
                {new Maze(1,0,0),new Maze(1,1,0),new Maze(1,2,0)},
                {new Maze(2,0,1),new Maze(2,1,0),new Maze(2,2,0)}
        };*/
        MazeGame mazeGame = new MazeGame(mazes);
        mazeGame.start();
    }
}