递归算法实战：迷宫问题和八皇后问题的思考与理解

简介：

迷宫问题

迷宫是非常常见的游戏，我们要从（1，1）入口出发，到达（8，8）出口，本文拟使用递归实现迷宫游戏，让计算机帮助我们找到一条路

实现思路

首先建立地图，使用二维数组来模拟地图，数组中数值为0时候表示该地方没有走过，为1表示红色的围墙，为2表示走得通，为3表示该路是死路
到达一个地方的时候，我们先使其数值为2假设走得通，再去判断该位置的上下左右位置是否能走通，如果都走不通就置当前位置为3，是一条死路
当出口处的数值为2的时候表明到达终点，游戏结束

代码实现

import java.util.Random;

public class MazeGame {

    public boolean setWay(int[][] map,int i,int j,int endPoint_i,int endPoint_j){
        /*
         * @描述: 判断当前位置各个方位是否有路可走
         * @参数注释:
         * @param map 二维数组当做地图
         * @param i
         * @param j [i,j]表示当前位置
         * @返回值 boolean 返回值为true就说明有路可走，否则无路可走
        */

        //如果终点（6，5）数值变成了2，说明路径形成，直接返回true
        //if else用来保证终点一旦到达就不用进行判断回溯了，不会像八皇后那样不停的返回所有路径
        if (map[endPoint_i][endPoint_j] == 2){
            return true;
        }
        else {
            //如果当前路没有走过就走上去，直接置其数值为2
            if (map[i][j] == 0){
                	//首先把当前通路设置成2
                map[i][j] = 2;
                	//再来判断各个方向是不是可以走通
                	//先判断下方有没有路
                if (setWay(map,i+1,j,endPoint_i,endPoint_j))
                    return true;
                	//判断右方有没有路
                else if (setWay(map,i,j+1,endPoint_i,endPoint_j))
                    return true;
               		//判断左方有没有路
                else if (setWay(map,i,j-1,endPoint_i,endPoint_j))
                    return true;
                	//判断上方有没有路
                else if (setWay(map,i-1,j,endPoint_i,endPoint_j))
                  //判断下方有没有路
                    return true;
                
                else{
                  //如果都没有路，那就是死路，置为3
                    map[i][j] = 3;
                    return false;
                }
            }
            else
                return false;
        }
    }
		
  	//该方法用来打印地图
    public void printMap(int[][] map,int ROW,int COLUMN){
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COLUMN; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

}

public class StartMazeGame {
    public static void main(String[] args) {
        //定义地图的大小，也就是二维数组的大小
        final int ROW = 10;
        final int COLUMN = 10;

        //定义迷宫的起始点（1，1）和终点（6，5）
        final int startPoint_i = 1;
        final int startPoint_j = 1;
        final int endPoint_i = 8;
        final int endPoint_j = 8;

        //定义地图
        int[][] map = new int[ROW][COLUMN];
        //设置路障第一列和最后一列设置为1
        for (int i = 0; i < ROW; i++) {
            map[i][0] = 1;
            map[i][COLUMN - 1] = 1;
        }
        //设置路障第一行和最后一行为1
        for (int j = 0; j < COLUMN; j++) {
            map[0][j] = 1;
            map[ROW - 1][j] = 1;
        }

        //设置更多围墙
        map[3][1] = 1;
        map[3][2] = 1;
        map[1][8] = 1;
        map[7][1] = 1;
        map[7][2] = 1;
        map[5][3] = 1;
        map[6][3] = 1;
        map[2][4] = 1;
        map[2][6] = 1;
        map[2][7] = 1;
        map[3][4] = 1;
        map[4][4] = 1;
        map[4][5] = 1;
        map[4][7] = 1;

        //开始打印地图
        System.out.println("初始的地图为：");
        MazeGame maze = new MazeGame();
        maze.printMap(map,ROW,COLUMN);

        //开始走迷宫
        maze.setWay(map,startPoint_i,startPoint_j,endPoint_i,endPoint_j);
        System.out.println("走完迷宫后的地图为：");
        maze.printMap(map,ROW,COLUMN);

    }
}