首页 > 其他分享 >递归的概念以及迷宫问题

递归的概念以及迷宫问题

时间:2022-10-06 21:34:35浏览次数:85  
标签:map return 递归 int 迷宫 概念 setWay

1、概念

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

2、能解决的问题

数学问题

  • 八皇后问题
  • 汉诺塔
  • 求阶乘
  • 迷宫问题
  • 球和篮子

各种排序算法

3、规则

  • 方法的变量是独立的,不会相互影响的

  • 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据

  • 递归必须向退出递归的条件逼近,否则就是无限递归,出现 StackOverflowError

  • 当一个方法执行完毕,或者遇到 return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或

    者返回时,该方法也就执行完毕

4、迷宫问题

思路

  • 用一个二维矩阵代表地图
    • 1代表边界
    • 0代表未做过该地点
    • 2代表走过且能走得通
    • 3代表走过但走不通
  • 设置起点和终点以及每个地点的行走策略
    • 行走策略指在该点所走的方向的顺序,如 下->右->上->左(调用寻找路径的方法,使用递归)
  • 每次行走时假设该点能够走通,然后按照策略去判断,如果所有策略判断后都走不通,则该点走不通

图解

初始地图,假设圆点为终点

 

 如以下->右->上->左的策略,路线如下

 

 代码

public class MiGong {
    //用0表示没有走过的路,用1表示墙
    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;
        }
        for (int i = 0; i < 8; i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        System.out.println("迷宫地图:");
        for (int i = 0; i < map.length; i++){
            for (int j = 0; j < map[0].length; j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        setWay(map,1,1);
        System.out.println("启动走迷宫后:");
        for (int i = 0; i < map.length; i++){
            for (int j = 0; j < map[0].length; j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }

    /**
     * 用2表示走过的路,用3表示走过且不能继续走下去的路
     * @param map 表示地图
     * @param i   表示第i行开始找
     * @param j   表示第j列开始找
     * @return    返回true的时候表示可以走,返回false的时候表示不能走
     */
    public static boolean setWay(int[][] map, int i, int j){
        if (map[6][5] == 2){//设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 {//非0的情况可能是1、2、3,直接false
                return false;
            }
        }
    }
}

  结果:

 

标签:map,return,递归,int,迷宫,概念,setWay
From: https://www.cnblogs.com/wyh518/p/16758549.html

相关文章

  • Fibnacci数列递归实现
    1.什么是Fibnacci数列?斐波那契数列(Fibonaccisequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(LeonardoFibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指......
  • Prometheus 快速入门教程(五):Prometheus 的关键概念
    前面几篇文章,我们单刀直入地讲解了Prometheus能做什么。接着用一个例子来让大家知道如何使用Prometheus,以及如何进行告警配置。最后,还用了一篇文章来讲解如何进行图表配......
  • 链表----相关概念
    1.结点:一个数据域一个指针域2.链表:顺序表的链式存储3.单链表、双链表、循环链表:结点只有一个指针域的链表,称为单链表或者线性链表结点有两个指针域的链表,称为双链......
  • 消息队列 基础概念
    消息队列基本概念什么是消息队列异步通讯的中间件:存放消息的容器。当我们需要使用消息时,取出消息供我们使用。消息是一种数据结构(当然,对象也可以看做是一种特殊的消......
  • 对于函数递归的理解
    递归的代码操作就是在自己未完成的函数之中调用自己这样看起来是并不合理的,因为在一个为完成的东西之中使用他自己,是不太现实的但是如果从代码执行的逻辑来进行理解的话,......
  • 算法竞赛备赛之浅谈递归
    递归递归需要有基例、递归前进段和递归返回段(return语句),是一种程序设计技巧,可以使程序编写简单,但实际上要付出低效率的代价计算时间复杂度常用数据的记忆(程序设计基本功,......
  • 程序员必备的基本算法:递归详解
    前言递归是一种非常重要的算法思想,无论你是前端开发,还是后端开发,都需要掌握它。在日常工作中,统计文件夹大小,解析xml文件等等,都需要用到递归算法。它太基础太重要了,这也是为......
  • Java方法(递归)
    递归就是A方法调用A方法,就是自己调用自己利用递归可以用简单的程序来解决一些复杂的问题。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求......
  • python基础--基本概念
    1.脚本的文件格式  脚本名.py  eg:hello.py2.脚本结构  大概三部分,脚本头+导入部分+业务模块  每一块都是非必须的,按需填写即可;    为了书写规范,一般......
  • TZOJ 6948: 走迷宫/深搜模板
    描述 有一个迷宫,图案如图5.2.6所示,红色区域表示不能通行,蓝色区域表示能通行,在迷宫中通行的方向是上下左右四个方向。从入口(1,1)位置进入迷宫,编程判断能否从出口位置......