Java实现迷宫问题(递归实现)

x33g5p2x  于2021-12-15 转载在 Java  
字(1.5k)|赞(0)|评价(0)|浏览(361)

问题由来

问题的描述

有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起点出发,如何找到一条到达终点的通路。

思路分析

本文通过按照约定的策略(比如下->右->上->左)不停的递归调用方法寻找迷宫的出口。从起点出发,每个位置都有四种选择(上右下左),先选择一个方向(按约定的顺序选择优先方向),如果该方向能够走下去,那么就往这个方向走,当前位置切换为下一个位置。如果不能走,那么换个方向走,如果所有方向都走不了,那么就回到到上一个位置去。一直这样执行下去,如果当前位置是终点,就退出程序

  • 用二维数组来模拟迷宫地图
  • 1代表墙壁
  • 0代表该位置可达。
  • 2代表每走过一个位置就将地图的对应位置标记 以免重复
  • 3代表走过这个位置但是走不通

代码实现

public class MiGong {
    public static void main(String[] args) {
        int[][] map = new int[8][8];
        /** * 初始化迷宫 */
        for (int i = 0; i < 8; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
            map[i][0] = 1;
            map[i][7] = 1;
        }
        for (int i = 0; i < 4; i++) {
            map[3][1+i] = 1;
            map[5][6-i] = 1;
        }
        System.out.println("======迷宫形状======");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        getWay(map,1,1);

        System.out.println("======行走轨迹======");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static boolean getWay(int[][] map,int i,int j){
        if (map[6][6] == 2){              //已经到达终点
            return true;
        }else {
            if (map[i][j] == 0){          //当前位置还没走过
                map[i][j] = 2;
                if (getWay(map,i+1,j)){  //向下走
                    return true;
                }
                if (getWay(map,i,j+1)){  //向右走
                    return true;
                }
                if (getWay(map,i,j-1)){  //向左走
                    return true;
                }
                if (getWay(map,i-1,j)){  //向上走
                    return true;
                }else{
                    map[i][j] = 3;         //四边都走不通
                    return false;
                }
            }else{                         //如果不是0就说明过不了或者走过了
                return false;
            }
        }
    }
}

结果输出

由于按照下->右->上->左的约定顺序取判定下一步是否可走
在到达(4,5)位置时会向向右走黄色的那条路线 当走到(1,2)
位置时四周都不为0即四边都不可走那么它就会退回到上一个位置
回到(1,3)后发现四周依旧不可达依此规则直至回到(4,5)
最终行走的路线就为红线所示

按照不同的策略有不同的行走路线

相关文章