您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

递归回溯-迷宫问题(Java)

递归回溯-迷宫问题(Java)

文章目录

    • 递归回溯-迷宫问题(Java)
      • 1.概念
      • 2.运行机制
      • 3.递归调用规则
      • 4.应用场景
      • 5.递归必须遵守的规则
    • 迷宫问题

1.概念

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

2.运行机制

在这里插入图片描述

在这里插入图片描述

3.递归调用规则

1)当程序执行到一个方法时,就会开辟一个独立的空间(栈)

2)每个空间的数据(局部变量),是独立的(四个栈虽然都是n,但是值是不同的)

4.应用场景

1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
2)各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等.
3)将用栈解决的问题–>递归代码比较简洁

5.递归必须遵守的规则

1)执行一个方法时,就创建一个新的受保护的独立空间(栈空间) — 默认遵守了(main)
2)方法的局部变量是独立的,不会相互影响, 比如n变量
3)如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.(上图堆中的)
4)递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError,栈溢出)
5)当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

迷宫问题

利用递归回溯算法找到出口

package DataStructures.Backtracking;

public class Maze {
    public static void main(String[] args) {
        //创建一个二维数组,模拟迷宫地图
        int[][] map = new int[8][7];

        //1表示墙
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        //左右为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
        map[1][2] = 1;
        map[2][2] = 1;

        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 7; ++j) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }


        setWay(map, 1, 1);

        System.out.println();

        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 7; ++j) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

    }


    /**
     * @param map
     * @param i
     * @param j
     * @author ZJ
     * Description
     * date 2022-05-05 17:28:45 17:28
     */
    /*使用递归回溯,让球找到出口,注:i,j表示坐标(1,1)
    图形上为0,表示没走过,1表示挡板,2表示可以走通的路,3表示走过了
    行走路线:下,右,上,左,如果无法走通,则递归回溯
    找通返回true,否则false,最后返回出新迷宫图形
    */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {//到达出口
            return true;
        } else {
            if (map[i][j] == 0) {//还没走
                map[i][j] = 2;//假设走通了
                if (setWay(map, i + 1, j)) {//向下
                    return true;
                } else if (setWay(map, i, j + 1)) {//向右
                    return true;
                } else if (setWay(map, i - 1, j)) {//向上
                    return true;
                } else if (setWay(map, i, j - 1)) {//向左
                    return true;
                } else {//都走不通
                    map[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }
}

alse;
}
} else {
return false;
}
}
}
}



分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进