铭记:

源码下载

一、迷宫问题

• 从黄色圆圈开始出发，走到红色⭕️表示走出迷宫
• 数字0：表示该位置没有走过，可以走
• 数字1：表示墙或者障碍物，不可走
• 数字2：表示该位置已走过，可以走通
• 数字3：表示该位置已走过，但是走不通

迷宫问题.png

1、解决迷宫问题的思路

• 走迷宫的原则：按照 下 —— 右 —— 上 —— 左 的规则来行走
• (1, 1) 值为0，表示没有走过，可以走并且设置(1, 1) = 2；按照规则应该向下走
• (1, 2)值为0，表示没有走过，可以走并且设置(1, 2) = 2；按照规则应该向下走
• (1, 3)值为1，这是障碍物，不能走，所以要不能继续向下，需要向右走
• (2, 2)值为0，表示没有走过，可以走并且设置(2, 2) = 2；按照规则应该向下走
• (2, 3)值为1，这是障碍物，不能走，所以要不能继续向下，需要向右走
• (3, 2)值为0，表示没有走过，可以走并且设置(3, 2) = 2；按照规则应该向下走
• 。。。
• 通过分析可以得出结论
  • 1、只有当前位置的值为0时，首先要把该位置值设置为2，再按照规则继续走
  • 2、当按照规则走时，向下走不通是，再试向右走，如果向右走不通，再向上走，如果向上走不通再向左走，如果左也走不通。表示该位置(2)不能走，所以需要回退（3）

代码 Migong

package com.raven.alg.s5recursion;

/**
 * 0：可以走的路
 * 1：代表墙
 * 2：走过的路
 * 3：回退的路
 * 迷宫
 */
public class Migong {

    public static void run(Integer size, int startX, int startY, int endX, int endY) {
        if (size < 1) {
            throw new RuntimeException("迷宫不能小于0");
        }
        // 1、创建迷宫
        int[][] mg = initMigong(size);
        // 迷宫围墙
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(mg[i][j] + " ");
            }
            System.out.println();
        }

        // 2、走迷宫
        go(mg, startX, startY, endX, endY);
    }


    /**
     * 初始化迷宫
     * <p>
     * 0：未走过，可以走的路
     * 1：代表墙
     * 2：走过的路，可以走得通
     * 3：走过的路，但是走不通
     * <p>
     * 规则：下->右->上->左
     *
     * @param mg     迷宫
     * @param startX 开始的x位置
     * @param startY 开始的y位置
     * @param endX   结束的x位置
     * @param endY   结束的y位置
     */
    private static Boolean go(int[][] mg, int startX, int startY, int endX, int endY) {
        System.out.println("=====开始走迷宫====");
        for (int i = 0; i < mg.length; i++) {
            for (int j = 0; j < mg.length; j++) {
                System.out.print(mg[i][j] + " ");
            }
            System.out.println();
        }
        // 代表找到出口
        if (2 == mg[endX][endY]) {
            return true;
        } else {
            // 该路没有走过
            if (0 == mg[startX][startY]) {
                mg[startX][startY] = 2;
                // 规则：下->右->上->左
                if (go(mg, startX + 1, startY, endX, endY)) {
                    return true;
                } else if (go(mg, startX, startY + 1, endX, endY)) {
                    return true;
                } else if (go(mg, startX - 1, startY, endX, endY)) {
                    return true;
                } else if (go(mg, startX, startY - 1, endX, endY)) {
                    return true;
                } else {
                    // 回溯，把 2->3
                    mg[startX][startY] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    /**
     * 初始化迷宫
     *
     * @param size
     * @return
     */
    private static int[][] initMigong(Integer size) {
        if (size < 1) {
            throw new RuntimeException("迷宫不能小于0");
        }
        // 创建迷宫
        int[][] mg = new int[size][size];
        // 迷宫围墙
        // 1、上下墙
        for (int i = 0; i < size; i++) {
            mg[0][i] = 1;
//            mg[3][i] = 1;
            mg[size - 1][i] = 1;
        }
        // 2、左右墙
        for (int i = 0; i < size; i++) {
            mg[i][0] = 1;
            mg[i][size - 1] = 1;
        }

        // 3、中间障碍
        mg[3][1] = 1;
        mg[3][2] = 1;
        mg[3][3] = 1;

        return mg;
    }

}

测试类RecursionDemo

package com.raven.alg.s5recursion;


import java.math.BigDecimal;

public class RecursionDemo {

    public static void main(String[] args) {
//        BigDecimal factorial = Recursion.factorial(20);
//        System.out.println("factorial = " + factorial);

//        Migong.run(10, 8, 8, 1, 1);
        Migong.run(10, 1, 1, 8, 8);
    }
}