java实现老鼠出迷宫

如图一只小老鼠从起点通过一些障碍到达终点，四周的墙壁不能通行，求通过计算得出迷宫路径，使老鼠成功逃出迷宫

算法设计 

①分而治之思想：

首先将老鼠出迷宫问题分成两部分求解，第一，迷宫的设计，第二，迷宫的解法。

迷宫设计：

看到一张矩形图，我们就要想到二维数组，一种抽象的一维数组，通过二维数组即可生成一张迷宫的框架，其次就是障碍的设置，通过对二维数组一些位置进行赋值，即可生成障碍，这样一张迷宫基本就生成了。

迷宫解法：

设计好迷宫之后，就要找出算法来求解，已知老鼠的行进方向有上下左右四种方向，我们在规定好老鼠的起始位置和终点位置后，可以设计老鼠行进路线，假设老鼠从起始位置开始行进（按照默认顺序下右上左），每经过一个坐标就进行标记，当遇到障碍后按照默认顺序折返，在重复之前的动作，即回溯，通过不断回溯最终就会到达指定位置，此时路径留下的坐标就是迷宫的路线解。

②回溯递归思想：

通过上面的迷宫解法也很容易知道递归思想的运用，我们已知迷宫的入口，结合老鼠的行进动作（下右上左）以及障碍的干扰，先得出老鼠第一步路线，先向下判断有没有障碍，没有则继续向下走，如果遇到障碍则向右进行判断有没有障碍，若没有则向右走，此时在向下判断有无障碍，没有则向下走，通过不断回溯递归就能得出一条路线。

具体代码

import java.util.Scanner;
public class migong {
    public static void main(String[] args){
        AA size  = new AA();
        Scanner print = new Scanner(System.in);
        System.out.println("请输入地图的长和宽");
        int length = print.nextInt();
        int wide = print.nextInt();
        int arr[][] = size.map(wide,length ); //调用函数制作地图并将结果传递给main中数组
        //遍历二维数组
        System.out.println("地图如下：");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println(); //每输出一层换行
        }
        System.out.println();
        BB find = new BB();
        System.out.println("请输入老鼠的起始位置（x>1）:");
        int start1 =print.nextInt();
        int start2 =print.nextInt();
        find.findway(arr,start1,start2,wide,length);
        System.out.println("通关路径如下：");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println(); //每输出一层换行
        }
    }
}
class AA{ //地图表示方法(1代表障碍 0代表空路 2代表路径 3代表死路)
    public   int[][]  map(int n1,int n2) {
        int arr[][] = new int[n1][n2]; //定义二维数组大小
        //第一行和最后一行为置为1
        for (int i = 0; i < n2; i++) {
            arr[0][i] = 1;
            arr[n1-1][i] = 1; //这里要减1目的是与下标一致
        }
        //第一列和最后一列为置为1
        for (int i = 0; i < n1; i++) {
            arr[i][0] = 1;
            arr[i][n2-1] = 1;
        }
        //设置路障
        arr[3][1] = 1;
        arr[3][4] = 1;
        arr[5][2] = 1;
        return arr;  //返回arr数组给main方法
    }
}
class BB{  //寻找路径方法
    public boolean findway(int arr[][],int m,int n,int x,int y) { //定义m，n为起始位置
        if (arr[x-2][y-2] == 2) {
            return true; //设置通关路口为右下角(角口)
        } else {
            if (arr[m][n] == 0) {   //当这个位置为0时代表可以走
                arr[m][n] = 2;  //用2来表示走过的路径
                //定义行走的路径顺序（下>右>上>左）,采用回溯递归思想。走不通就回头
                if (findway(arr, m + 1, n,x,y)) {
                    return true;
                } else if (findway(arr, m, n + 1,x,y)) {
                    return true;
                } else if (findway(arr, m - 1, n,x,y)) {
                    return true;
                } else if (findway(arr, m, n - 1,x,y)) {
                    return true;
                } else {
                    arr[m][n] = 3; //表示死路
                    return false;
                }
            } else {   //如果没通关继续此时坐标为1，2，3
                return false;
            }
        }
    }
}

总结

①通过两个方法，地图制作，迷宫求解，实现了对数据的封装，大大简化了问题的复杂度

②，通过一个问题，将多种知识串联起来，for循环，数组内存分配，类和对象以及传参机制等等

③通过动态开辟数组，以及传参，输入，将方法联立起来，提高了内聚性，同时也使得程序能更加灵活（可以定义迷宫大小，老鼠初始位置，障碍设置）