00:00
好,我们先把这个图拿到这边来。我们首先还是要分析思路。OK,来,同学们,现在呢,我们有一个迷宫。我们来解决这个迷宫问题。迷宫回溯。离宫回溯。那你在解决一个问题的时候,你首先要做的是思路分析。然后才是代码实现。对吧,你思路没有,那你先不要去写代码。我说这个这个我没有什么思路啊。那就没办法了,说老师我这个没有思路,你的思路怎么才会有呢?只有多看多写。多去看人家源代码,或者多看书,没有别的办法,比如说你在听课,这就是一个学习,比韩老师讲过了哦,再遇到这种类型类型的问题,我绝对没问题了。大家在听课的时候一定要这样解决,这样听啊,就说。推要类推。类推,比如说韩老师讲了一个迷宫问题,那么这一一类型的这种回溯你都可以解决。
01:02
你不能说我讲了一个迷宫,那下次稍微变化一点,我做不出来。那就麻烦,但是如果你你是这样的人也不要着急,如果你是真的是,就说我说一个你就能知道一个,你只有一个办法解决了,那那你只能比别人看的更多。你别人比看的更多,那么那我看见多识广吗?那等到我们再看一个算法的时候,我马上就想出来,我曾经在什么时候看过这个算法,马上就上了。你们现在很缺这个东西。对,因为你们现在玩大数据,要这个工资,如果说同学们要要想拿到一万五问题不大,就你把我们这边学的东西啊,学的东西把Spark啊,什么这个map produce啊,这个哈杜学的差不多一万五六,理论上说应该也能找得到。但是你要拿两万五或者三万五或者45000。那同学们,听老师一句话,光靠你那点东西是拿不到的。那肯定拿不到啊,说好是真的拿不到嘛,肯定拿不到,因为那个时候别人问的问题肯定要要你去解决一些,就是出就说刚刚入行的那次你解决不了的,那这个时候你要靠什么。
02:08
那肯定要靠你的一些能力了,对吧?好,所以说你要多看,这是老师给大家一个忠告啊,多去看一下,那现在我来分析一下思路,首先。第一步,我们先去创建,创建一个二维数组。二位数组我要干什么呢?表示这个地图没问题吧,哎,表示这个地图。表示地图没问题。那么这个地图里边呢,我们要约定。我们要约定什么呢?用不同的数字来表示它的含义。那我现在要做一个约定。我要约定什么玩意儿呢?我约定如果是一,这个值约定如果元素的值,注意听元素的值为一,就表示是一个四度墙。强什么意思,就?就不能走,那么如果是零啊,我我就按这个顺序来写吧,零。
03:04
表示可以走,还没有走。可以走,还没有走过。注意听啊,就说这条路还没走过。就是你不是在你在回溯在探测吗?说零表示没有走过,一表示强,二表示什么呢?二表示通路。表示通路。表示通,呃表示走过了,而且可以走的是可以走,就是以后你后面最后最后形成的线是二,只是二的就可以,一条线就可以走过去了,还有一个三。这个大家很难想到。我待会还有个数叫山,这个山表示走过了,但是这是一条死路,只要走到这儿,一定是出不去的。哎,老师,为什么这还有个死路呢?因为这个迷宫里面肯定打个比方个比方,将来假设我们这我们这有个这么一个情况啊,同学们注意听,假如我这个地图是这样长的。
04:04
这个地方也是用一个墙挡住的啊。你只要敢走到这儿。你肯定是不论怎么就出去。对吧,但是有有没有可能你回溯到这个位置来呢,有可能。因为你假设你就是这样,走走走,绕过去,往这儿探了一下,说这地方我们还要规定有一条路你走过了,但是是条死路。表示已经走过。走过,走过了。走过,但是是条死路。啊,走过,但是是死路。死路就是走不通。OK好,那现在呢,这个基本的基本这个约定我们就有了,这这地图我们知道去讲了第三点,我们来说一下这个策略。因为你整个这个过程是实际上是一个递归的过程,那么我怎么递归呢?我先定一个策略,我在写代码的时候再递,递归回溯式。
05:02
呃,这个可能现在大家还递归,大家现在应该理解了。但是回溯大家可能还不太理解什么叫回溯,回溯待会儿只能看代码才才能看到这个回溯的一个现象啊,那么这个递归回溯我们我们这个走,我们现在确定一个。确定一个这个策略。什么叫策略啊,说同学们,我我们考虑这样一个情况,就说现在你们去玩迷宫游戏,现在不是比较流行的,就是有些有些人开一个什么一个密史吧,好像叫对吧,密室,然后你进去过后,让你让你在里面走出来,那你你你进去过,你你是怎么走的。你会,你有策略吗?说我没有策略,我不管那么多是吧,我反正就是,呃,我就我就我就瞎撞。那你肯定是出不来的,你肯定是有策略的。对吧,有些东西说我一直摸墙。
06:00
幕墙能出来吗?那个。是不是一定能出来啊。不一定对吧。也不一定能出来。说这个摸墙呢。这个大家可以去试一试,那么现在我们要定定一个策略,我们先先这样定一个策略,我们先走上面我们先下。向下下面走一走,看能不能走通,如果下面走不通呢?A下面走不通,我我看一下我这是怎么定的啊。我这样听的。下啊,我们我们先定这个策略下右上左,因为待会我一是按这个讲的,我们先往下走,看看能不能走通,如果走不通,我们再来看他这个右面能不能走通,右面走不通再走上面,上面走不通。我们再走左边。但这里面有个问问题,就说你走,比如说你这个,你在这个点下面能走通。比如说你在地方,这个地方下面能走通,走完了过后。
07:00
但是你你你下来过后又发现这地方是个死,怎么办呢?就要回去。你假设这样一个情况啊,同学们。我这是下右上左,假设我们这个地主长这样子的。同学们假设一个地转,这样我先下来了。你下来是不是最起码走到这死路啊?你在这个地方是不是又在这个点又有策略,就是在每一个地方,在这个点你又开始在这个点又执行下,又上走,再往下走不通。再向右走不通,再向上。走过了那。这个时候就要考虑回溯,就说你这个点如果走了又回不去,你还回来发现你原先在这个位置,注意听这句话啊,你你原先这个。假设我先测一下。我们假设到了下面来了,到了下面过后,我在这个点又开始执行下,右上左。
08:01
我们发现。都走不通,这个时候呢,我们要回到上面这个点。回到这个生命点,我们刚才已经探测了下,是不是这个时候就可以尝试向右边走了?于是他这边就走通了。也就是说这个就叫回溯。好,那么下右上左策略就有了,好,同学们现在有了这个基本的东西过后,我们就走代码了。就基本的思路我已经说完了,现在我们走代码,打开我们这个。Serve,我们直接写的,那叫迷宫。注意听啊,我这个代码并不难。但是但是就说你要把它理解了才有意义,说代码要理解了,能够做到类推,这个就好办了,那我怎么来写这个这个东西呢?来同学们,我们先搞一个地图,没有地图你肯定。没法验证你写的是对还是错吗?所以先做一个地图。OK。
09:00
做一个地图看看啊,这因为有时这些地方经常会掉线。先做一个地图,这个地图我们就把它画成跟我们这个一模一样,那同学们这个红色的就用一表示,这个没有走过的就是零表示,好同学们,那现在我们先做一个地图V,我们就叫这个叫什么呢?叫做这个就叫就叫map吧,好吧,就叫map。就叫迈步好,然后这个呃,地图二维数组,大家还记得是怎怎么怎么创建的吗。然后这个地方我们写写写几和几啊,应该是八和七。我看是不是啊,几行几列12345678887没问题,八七好,然后这个地方是不是要指定一个类型呢。A,要指定一个类型,我们就用零,好同学们,嗯,在你没有做任何处理的时候,是不是它所有的元素都是零了,好,现在我们先把那个上面。
10:03
上面就是上面那一截。就是这上面我们全部标成一,上面和下面全部标成一把上面。全部质疑。全部之一。之一的目的我就不用说了。然后再把左右两边。上下啊,我们先把上下。上下全上下全部之一,然后左右。左右全部之一。表示强嘛,那现在我要开始做了for循环。哎哎,同学们怎么把它全部之一啊,上下我们来看看上面这一截是不是它的横坐,就是它的行不变列在变化。下面是不是也是它的,呃,这个行不变列的变化好,那么上面这个是零七,好,这个就也很好写,那开始写了啊。
11:02
啊,On until until,这个是多少?先暂时不写。下面开始写,那就是这个map map,它的零,下面这个是I。等于一好好这个I,同学们看这个I应该是从这儿到这儿,就是1234567,所以说我这儿只要写个七就可以了。哎,同学们,这样大家知道什么全部之一了,就最上面就全部之一了,能能理解吗?好,然后我们再把这个下面,下面是不是七啊好,再来全部之一。好,现在呢,我们把这个地图先打印出来,看一下原始地图。打印一下地图。打印地图注意听啊,那现在打这个地图也很简单,我们遍历一下就可以了,各位同学遍历一下就可以了,For循环I,我这里就简单一点啊,就是直接把这个数字写上了。
12:00
呃,当然UNT,我们是航四八。OK。行四八,然后呢列。五再来负循环。OK,企。走零。列士七,UN7,各位同学。好,然后呢,我们把这个力度打出来print,呃,这个print不不能马上换行啊,换行你看出来就非常奇怪了,然后这边呢,我们就把这个词打出来,就是map。里面是I。且。IG,然后呢,为了好看,我们打一个空格,整个这个一行打完了过后我们来一个换行,好,这个代码都非常简单,抛下。运行,我们先看看现在长的样子,跟我们想的一一不一样。我们发现呢,现在长的样子跟我们想的应该是一样的,就是上下背全部置为了一没问题吧,没问题,OK,那同样我们还要把左右两边全部之一。
13:01
OK,那左右两边呢?同学们想一想。实际上左右两边是这边和这边,那么它的什么不变呢?它的列不变对不对,那列这边是零,这边是七是不是,所以说你可以先把这个写出来,写代码,不要较劲,不要非得把这想出来,怎么写这些下面。很多同学喜欢。这个总是顺序思考。你顺序思考的带来的后果就是。有时候想不想不进去,你们看你们,你们考试的时候有些同学,我看我们以前高考的时候,有些哥们本身平时学的不错,他高考高考的时候,人家出题的时候,有有一个题特别难,他就挡在这,有些哥们儿他就强迫症,你知道吗?这个题做不出,做不出来我绝不做下个题。结果考的很差,你看我当时考试就很聪明,那这个数学。先做下面的嘛,后面发现最后那个分高的反而很简单批啪做完了,最后心里面很稳当了,然后再回头做那个难的题,所以你写代码也有也有这种思路,就说先不知道怎么写,我们先把这个能写的写了。
14:05
是吧,这个我也不知道怎么写,但是我知道这个列是固定的对不对,好,这就第一个就写出来了,然后这边我也是个变量,那这边应该是几呢?这边是七是不是各位同学是七吧。是七还是几啊?六吗?看一下啊,01234566啊,同学们说的很对,16很好啊六因为它的列是列是七个,但是它的下标最多就是六了,好,现在这个地方是不是大家就明白应该怎么写了呀,是不是就很简单了,就ii小于零零。啊,Until是不是八了呀,为什么是八大家知道吧,因为你这个前面就是这样子的嘛,零零到零到七,但是八五不取,所以我就把这个I存进去。好,这个是这边把这个I填进去,然后这边是不是我们把字为一啊,待会就写完了,看多简单。
15:04
说你不要老是那样去硬想。这个一写代码又出来了。是不是两头都两头都跑起来了。就这么简单,就是有时候不要去较劲啊,不要较劲好,紧接着呢,我们还有个事儿,各位同学,我们还有个什么事呢。是不是还要设挡板呢?是这个地方是还有两个挡板要设一下挡板,我们看这个位置是什么,同学们能看出来是几和几吗?三一和三二对不对,还在设挡板。再设下挡板,因为我待会儿要测试嘛,设置挡板。好,挡板也非常简单,就是三一,我就因为这两个,呃,就两个,我就直接写代码了,Map。好,三二。这是我们的梁强。可以理解成。好,三二好,同学们再执行一下。好,这时我们可以看到地图呢,已经OK了。地图已经OK了,没问题吧,现在开始写代码了,核心代码就来了。
我来说两句