java递归实现迷宫出口问题

1. 题目描述

给定一个m*n的迷宫，随机给出障碍物，使得小球从起点可以走到出口

2. 迷宫设计

这个视自己喜好设定，障碍物也随便设点，使用二维数组模拟迷宫，1即为墙壁与障碍物

3. 思路分析

使用递归来模拟小球运动，假设小球从（1,1）开始，到（n-1,m-1）即为找到出口。 我们规定 2 为可以找到下一条路线的点，3 为四处无法行走的点，未走过的点为0. 行进方向自行规定，此处我使用顺时针，即上右下左。 当出口处为2，即出口处被标记为可行时，返回true，即可行。 当小球运动到没有未走过的点时，判断其上行是否可行，若上行可行，则进入递归，将坐标上移一位并且继续进行判定。右下左方向同上行。 如果不是0，则说明该路径不可行，返回false。

4. 代码

package com.nansl.stucts.recurrence;

public class Migong {
          
   
    public static void main(String[] args) {
          
   
        //声明地图  此处将迷宫大小写死，感兴趣的朋友可以改变迷宫大小
        int[][] map = new int[15][15];
        for (int i = 0; i < 15; i++){
          
   
            map[i][0] = 1;
            map[i][14] = 1;
        }
        for (int i = 0; i < 15; i++){
          
   
            map[0][i] = 1;
            map[14][i] = 1;
        }
        map[3][3] = 1;
        map[6][8] = 1;
        map[2][2] = 1;
        map[3][2] = 1;
        map[1][2] = 1;
        map[2][3] = 1;
        for (int i = 0; i < 15; i++){
          
   
            for (int j = 0; j < 15; j++){
          
   
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
        move(map, 1, 1);
        System.out.println("---------------------------");
        for (int i = 0; i < 15; i++){
          
   
            for (int j = 0; j < 15; j++){
          
   
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
    }

    /**
     * 定义行走规则：上右下左
     * 走过的可以走的路为 2  无路可走的地方为3
     * 当进行递归模仿移动时，前进的道路如果为 1 2 3 则返回false 即不可以通行
     * @param map 地图
     * @param i   横坐标
     * @param j   纵坐标
     * @return    当前道路是否能走
     */
    private static boolean move(int[][] map , int i , int j){
          
   
        //出口在6 5
        if (map[6][5] == 2){
          
   
            return true;
        } else{
          
   //如果没有找到出口
            //首先要判断这个点是否为没有走过得点
            if (map[i][j] == 0){
          
   
                //先将目前走到的位置设置为可行
                //如果上下左右走遍了都返回false 就会返回到本层递归中  则设置当前点为不可行3
                map[i][j] = 2;
                //先向上走
                if (move(map, i-1, j)){
          
   //如果向上移动返回为true 则返回true 向上移动则会继续递归调用下一层move() 相当于走了下一步 就这样如果有路会一直往前走
                    return true;
                }else if (move(map, i, j+1)){
          
   //向右移动
                    return true;
                }else if (move(map, i+1, j)){
          
   //向下移动
                    return true;
                }else if (move(map, i, j-1)){
          
   
                    return  true;
                }else {
          
   //向上下左右走都返回false 那么代表这个点不通，回到上一个点
                    map[i][j] = 3;
                    return false;
                }
            }else {
          
    //如果不为0  那么为 1 2 3 都是不可以走的
                return false;
            }
        }
    }
}