00:00
地图已经OK了,没问题吧,现在开始写代码了,核心代码就来了。核心代码是哪里呢?同学们,刚才老师已然把这个思路分析清楚,我们现在要来从第一步已经做完了,现在做第二步和第三步没有问题,来同学们,下面我们单写一个函数,因为递归一定是函数自己调用,所以说这个代码呢,来K啊,就是使用。使用递归回溯,回溯来解决来解决,来来找路来找路。OK,走路啊走路。呃,那么现在,诶这个呃,来找路啊,OK。那现在呢,我们就开始写一个写一个这个方法。这个名字我们就叫diff set。啊,名字随便取,反正我就要找路嘛,或者叫find的位都可以,无所谓,赛赛呢也可以,现在呢,我们要首先第一个你在进行这个找入的时候,首先把这个地图得给我。
01:04
这个没问题吧,你没有地图我肯定玩不了,是不是好地图,我们先拿到地图,那就是map。它的这个类型。对不对,是个二,但是这个二里面呢,大家看它是不是是一个二维,是一个二维数组啊。啊,说说说它这个arra array里面放的是什么呢?还是一个AR。这个能能看懂吗。它是不是这样子,呃,这样子的一种,呃一一种数组啊,就是这个二里面放的又是一个二位里面放的是in的,好,然后我们这边再要设置一个从哪里开始找,就是你能起始的I和节,那现在呢,我们来写一个I。结。OK,就写完了。那下面最后有没有找到我们返回一个布尔兹?
02:03
不定式,大家知道递归是必须要返回。递归是不是要必须要指定返回类型,好的,那待会儿呢,我我已经把这个说清楚了,一就说这个是代表我们的地图。因为你你肯定是要对这个地图进行回溯嘛,地图第二个。第二个这个I和节是代表我们从哪里开始找I节?埃及是指定指定从地图,地图的哪个哪个点开始出发。拿点点。开始出发。也,那也就是在我们这,在我们这应该是几和几呢,同学们。在我们这是不是就这个点就是一一,这个点在我们这应该是一一能理解吧。意义这个点,那为什么呃我不写死呢?因为将来这个是要不停的传递的,好,有了这个东西过后,下面我们就来看。
03:06
这个逻辑了。首先我们要判断什么时候。表示找到了呢。这个代码写出来,你还要给你们讲怎么理解呢?好,首先要这样写,如果首先我们判断什么情况代表找到路了,什么情况就代表没有找到路,如果我们的这个同学们啊,刚才。我是不是已经讲过一个重要的规则?我是不是确定了这么确定了这么一个规则。这个规则不是不是说吃饱了没事干在这写的啊,这个这个规则是对我们写代码非常关键的,那首先我们判断什么叫做找到了呢,是不是就意味着这个麦谱,如果这个麦的这个,呃,这个。这个值就这个点。这个点如果它等于二了。是不是就代表这个路已经找到了。就你只要这个地方都支撑二了,那肯定就没问题了。
04:03
也就这个地方,就是说我们这个这个点啊,就是这个点,这个点是六五,看清楚没有。就这个点,就是现在我见投资的点,如果这个656。五它等于了二说明什么问题?只要就说在你整个这个不停的这个回收,在设置这个标志的时候,只要这个六五设置成二了,那可以确定。这个路就已经找到了,那如果他没有没有四乘二,那肯定就有各种结果了,但是如果这个条件成立,则表示表示这个路已经通了,路已经。啊,已经通了,已经找到。那这个时候不用犹豫,不用彷徨,直接一个什么呀出就找到了。对,那A。Else,好,同学们,这个else这个逻辑呢,同学们要注意,这边情况就比较复杂,Else呢。
05:00
首先我们要判断当前这个地方是不是零。就说如果我现在当前的这个点。I截这个点。它等于零,请问各位同学,如果这个map I解等于零,表表表示一个什么意思同学们?是表示还没有走过,刚才不是讲过吗?可以走,还怎么样,没有走,这个我在前面已经定好这个规则了。就是回溯,你肯定先把规则定好,说如果这个map I j等于零,说明可以走,但是还没有走哦,这个地方我们先先写一个L4啊,待会还有用,我们先写到这。那么如果这个迈普I等于几等于零说明没有走,那现在我们就要开始在这里。这里递归和回溯是在这里发生的,因为只有是零的时候,我们才会去做操操作,这里开始这个递归啊,递归回溯。
06:01
递归。递归回溯。好,我上来先做一件事情,我上来过后先做一件什么事情呢?我先把它置为这个什么,大家知道吗。设为二高,有同学已经看懂了。我先认为可以走,但实际上他能不能走不知道。那就你怎么感知到它一定是个通道的,不着急,因为我要我要往后先探,就说我先把这个点设置成二,我表我认为我我认为啊,我认为是可以走通的,我认为是可以走通的,这条路这个点是可以走的,认为该点,我认为该点。该点这点啊,该点。该点。是可以走通的。但是他能不能走通不知道。二走通。走通的,但是我可以先把字为二,但是能不能走通不一定啊,但是但是不一定啊,不一定说待会儿呢,我就有一个回溯,不一定。
07:08
好,那么不管怎么样,我先制成一个二好,下面我又开始走了,我的策略就开始来了,就是在这个点过后,我。这个二到底能不能走通,取决于。就是我我在这个点,在这个点的点的基础上,往下往上走过后,它能不能通。对不对,所以说这个地方呢,我们就开始走一个策略了,我们的策略来了,同学们,我们的策略是刚才老师已然定好的一个策略。是上右下左。啊对对对,是下右上下右上左,好,我们先往左边找。就是在这个点先把它标记成可以走通,然后我继续往下走。那下面能不能走通不知道,如果他能走通,那这个二就说明这条路是合,如果不能走通,我们把把它再改啊,先向下走。
08:00
下周二。这个大家不用着急,就是你第一次听。啊,那么向下找是不是就这样子的。是不是我们只需要做一个动作,把这个map是不是要传进去。是不是也会把map给人家吗?然后再向下找把哪个改一下就可以了,是不是I加一就可以。然后节变不变不变没问题,好,然后这边呢,如果向下找整个这个它为真。是不是这边我们也返回一个出。返回一个处。好,但是向下找它有有没有一种可能性,就是向下找它没有通啊。是有可能没有没有通吧,没有通的话呢,我们就A。If,我们就接着执行我们的第二一个策略,向右走。就这这一点的基础,在这个点的基础上,我不是都走一圈向右找呢,这个代码也异常简单。
09:07
只需要把它放进去,向右找的话,是哪个变化。结怎么是爱呢?是结加一吧,是不是右嘛?右是不是这地方也返回一个错。没问题吧,好,然后这条路又没有,这条路也不知道能不能走通,所以说我也接着继续往下走。那么这个时候呢,我又向上继续再来找一下,因为按我的策略是这样的一个策略嘛,向上找同样的道理,把这段代码拿过来,然后这边呢是I减一截不变,就不要写错了,写错时的会很难看的。OK。然后最后。是不是?If还有一条没有走向左找。左早的话呢。大家看这边左脚是怎么怎么变化,是节减一。
10:02
也就是说现在我们测的是这个下右上左全部测过了,如果这个呢也能通,那也返回一个处。那问题来了,请问你这个这个这四个方向有没有一种可能性就是。都都不通啊。有没有,有没有这种可能性,有可能,当然有可能了。那这样这样一个情况,是不是意味着还有一个逻辑就是else,那这个情况同学们我问大家,此时此刻这个map I等于这个二当他回来过后。刚才回来只要进到这个else,我们大家有问题,根据根据刚才我们讲递归的原则,请只要进到这个else,请问这个这个地方的埃及是不是就上面这个值。就回过来了,我只需要把它制成一个山村,这条路走不通的。走不通。走不通,那么走不通的话呢,各位同学简单了,把这个字体改成三。
11:01
也就说这条路不能走了,你走不下去,你怎么走都通不了。不能走,走不了,然后你这是不是就马上给他返回一个force,这条路不要再走了,你再走就。死的很硬的。对不对,好,这个写完了过后,代码写完了吗?没有写完,还有一个这个情况,你进到这门,如果发现I解,在你遍历的时候,I解它不等于零。这个数是代表不等于零。如果听到这个就这两个是哪哪两个是对应的啊,这个大家看这一段代码是对应map等于零的,说明还没有走。但是如果我问大家,如果它不等于零,不等于零的话,请问这个map的值是什么?是哪几种情况?对,你看啊,同学们看,如果这个map不等于零。如果麦普I。我把这个道理讲清楚,这个不好理解,就在这里,就他需要你。
12:00
想象。如果map不等于零,它如果不等于零,我问大家,Map有可能值就这几个值,Map的这个值它就这样几个。啊,就是折纸。则。走这个词只能是这样几个一,肯定不能走吧。恐的二二是不是你已经走过,已经通了,你是不是没有必要再走了,都人家已经走过了,你说这个可以走,你还去走,不有病吗?还有一种可能性就是三。思路,那在这种情况下,其实对你来说没有义再走了,你就直接return一个force,就不要再就说我这个在城市没有意义的,就force一下就完了。代码就写完了。整个代码就写完了,大家看一下。周老师要代码写完了能用吗?我们来试一下吧。好来,整个这个逻辑就是这段代码呢,待会儿我们把这个代码跑起来,我们再来回顾一下,代码就写完,写完过后我们来测一下。
13:01
测试。测试我们的这个递归回溯方法。这是。测试这个这个方法好,测试这个方法呢,我就简单的写一下啊sideway,把这个map放进去,我们起始位置是一一。呃,这个时候因为map它是呃引用类型的,也就是说这个时候这个map你们应该想象到,如果按照这个图来说,他们每一个站,每一个站访问的这个空间,访问这个地图是同一个,所以说不需要改变,那下面呢。我们就把这个地图打一下就可以了,来打印出这个新的地图。打印这个新的地图,好,我们看一下这个路它是否已经找到了运行。当然你这个写的不好,他有可能是个死路啊好,我们看看,诶这个地方我我我打一个间隔线啊。间隔线,不然我这看的有点不清晰。
14:02
各位同学来跑一下。我们看这个代码。诶,大家看。对不对。是对的吧,而且我我们再问一个同学,假如我看大家听懂了没有啊,我现在把这个策略改变了。我把这个策略改变了,改变过后我请一个同学看看他这个造成这个通路应该是什么样子的。我这样改。大家同学们看啊,如果我把这个策略做一个改变。哎,我们把这个上上和下目改一下,比如说我把这个策略改成这样子的。修改策略。修改策略,假如我这个地方改成一个上,我我就测试一下啊,先走上。再走向。再走一下,好,如果是这样的话,请同学们思思考一下,我应该怎么改我的代码。
15:05
是不是第57行应该先把它改成上的话,应该是先减一。OK,好,这个就是上早。这个不用改下下找的话把哪个改一下。就是呃是I加一,好,同学们,如果我这样找的话,请同学们呃,思考一下,此时此刻这条路应该是怎么走的。它是不是这样走的,它先在这儿往上走,走不通,走不通,它是不是向右走了,于是一走通了,走通这面是标成二了,它又到这是不是它又向上走,是不是走不通,走不通他又走,是不是又走通了,于是它还是标成二,没有改成,然后他到这儿是不是又是一样的,最后走走走走这边全部是二。当他走到这儿的时候,他往上走走不通,向右走走不通,但是你要往下走。走通了吧,所以又到这儿,哎问他到这点会怎么判断,是不是他又向上走,但是是发现他这个二已经走过了吧,是不是他就直接不走了,就退出来,然后他又向右走,是不是走不通,向下走是不是又走通了,诶这样这样的意思,走走走走,你看最后如果按这个策略,它的线是这样子的,能理解吗?
16:22
好,同学们,我们跑一下。看看跟老师说的是不是一样啊,跑一个。来,各位同学。是不是这样子的,咋看?那说明我们这个策略和我们这个路径是有关系的,那如果我们将来要求这个最短路径,一个最笨的办法就是我们把所有策略都写一遍,便利这个策略,我们再把这个,把这个,把这个路径保存一个,保存的一个数组求认子,一求认子,谁的认子最小,最短路径就出来了。是不是这个道理,只是呢,我们如果要优化的话呢,还有很多方法,好同学们,这个就是我们的一个这个回溯,最后我在啊,我还没讲到回溯,还有一点回溯讲述讲完啊。
17:09
我们再举一个例子,看回溯是怎么发生的。就是你看这些都走过了,但是这条线是不是我一直没有没有走过。我们来走一个回溯,我们模拟一个回溯现象啊来。比如说我现在狠一点。我把这个和这个也标成挡板。我们看他是怎么走的。他会不会一步都不走呢?啊,把这两个标准挡板我们怎么标呢?这个是一二和二二,好的,我把这两个标准挡板看一下啊。我们来体体验一下这个用法,Map。麦。呃,刚才是二几啊,11212等于一,好map还有一个二二是吧,二二,我们看这个回溯它是怎么发生的,我就把这个讲完,咱们就不说了啊同学们。
18:02
好,那么这个时候我们运行这个结果,先问大家,你们觉得这个结果应该是什么样子的。是不是?是不是他会这样子,它会在它会在这个两个地方在这么标一个三。这边也标一个三,因为这边这边是挡板嘛。那我们先看看是不是这样子啊,还是说会发生一个什么死鬼啊什么的,大家看。我们发现它是这样走的。他其实也尝试着玩了一把。上三,那这个三三是怎么出来的呢?我们来看一看。首先。他向上上走,走不通。他肯定先把你标成二嘛,啊三万三那大也走不通,这地方走不通。啊,向下走是不是走通了呀,好。当他向下走的时候,请问这个时候这个点是不是就是二。没,没有问题吧。
19:00
没没有问题,那这个确实是确确实实是二,然后呢,他往下面又走到这儿来了,走到这儿是不是这个地方是真的是走不通的。是不是他会把这个点标成三,标成三过后这个站是不是要回回来呀。因为你站,因为这个真正他走的时候是往这边走的嘛,所以他回到这边来来过我发现都走不动,是不是还是执行那个要一句,因为因为他虽然有一条线走进去了,但是后面他不是还得。回来吗?回来过后是不是又把这个,又把这个当前这个二又重新改成三了。这就回溯。大家体会一下。就说怎么理解呢,就说这样理解啊,就说他在他在走这条线的时候,的确他的确找到了一个入口,就是比比如说这吧,往下走,他确是在第一层这个递归的时候,他走这确实进去了。进去他发现确实能能往下走一步,但是走完了过后,他发现后面这个走不通,他是不是又回来了,回来过后他又回到这一层,把原始之二的那个又重新改成三了。
20:07
它是这么一个回溯的一个过程,好了,同学们,那关于这个迷宫问题,我就讲了这么多,讲的比较细的,目的主要是让大家能够举一反三。我们截取了。
我来说两句