00:00
我们继续完成其实周游问题算法的代码,那刚才呢,我们已经把这一个核心的方法就是计算码,而下一步能走的位置写这一个方法写完了,下面我们接着来完成。那大家知道在我们整个。进行算法实现的过程中呢,我们要去用来标记某个棋盘的棋盘的某个位置是否被访问过,是吧?所以说我要创建一个数组来注意听我们。应该这么说吧,我们说创建一个属性,创建一个数组吧,创建一个数组干什么呢?来标记标记棋盘。棋盘的某个某个,呃,各个位置吧,各个位置是否被访问过,因为你访问过了,你你你才知道这个点它是第几步嘛,对不对,那显然是要用这个数组了,因此我写一个private。
01:04
Private。什么呢?还是static booing。对,然后是个VZT的对不对,是个数组嘛。好,我们还需要一个什么呢?同学们还需要什么?我们还需要来标记我们是否期盼的所有位置,是不是全部访问过了就是。再使用一个变量,使使用。二使用一个属性,属性标记标记是否棋盘。的所有。对。所所有位置,所有位置都被。都被访问过了。对,也就是说是否成功了。是否成功了,如果为为真就代表成功了,那private private sta什么呢?还是用个booing,那这个时候变量呢,我们就取个名字叫finished。
02:07
Finish,好,就是如果为错了,如果为处表示。表示成功,否则就代表没有成功,那下面有了这两个变量,有有了这两个信息过后呢,我们来写他的这一个棋马踏棋盘的这个核心算法,我们来把这个核心算法给大家写一遍来写到这一栏就写到这儿。那这个算法呢,我们这样取个名字,Public static void,不需要返回什么值,因为我们在整个过程中其实就是对棋盘的修改,是不是好取个名字叫做。TRY。Ver,手手就是旅行嘛,操手手什么呢?Che ches ball board boardd,那你在进行这样一个算法实现,或者说再让这个码儿去踏我们这个棋盘的时候,我需要几个几个参数传过来呢?首先第一个你要把棋盘传给我。
03:11
这个没问题是吧,这。Board。Bo Bo,没问题,Bo。这写错了,Bo。Boardd board棋盘给我另外一个是不是要告诉我你现在是在第几列?第几行啊?C Lu column,就是你现在这个马儿在棋盘的第几行和第几列,然后呢,现在是在处理第几步,明白意思吧,这个step就是刚才老师给大家分析的,每走一步呢,成功的话,我们就把这个step加一。就代表他是在一个棋盘里面做第几步,好,现在呢,我把这个方法做一个在说明这个就是完成马踏或者叫骑士。
04:05
其次,周游。周有问题的算法。那么这个其实呢,其实呃,其实board就是我们的棋盘,这个很好理解,这个代表马儿,马儿当前的位置的行,就第几行从零开始记的,注意啊,注意这是从零开始记,比如说你是第一行,其实这个若呢等于零,明白吧。好的,这个是马儿当前位置的列。列就第几列了,现在他是在我们这个棋盘的第几列明白,那么也是从零开始的,Snap表示马儿走的这是第几步是?是第几步,第几步。OK,那么注意听清楚啊,我们这个sta呢,它初始的位置是从一开始的。哦,就说初始,初始位置位置就是第一步,那以后就按这个增长就行了,比如下一步就第二步了,就是他走,他走第一步的时候,就是走第一步的时候就是第二步,因为他初始的位置就是才是它真正的第一步嘛。
05:18
只是呃,这个是我们指定的,好的,那这些有了功能,我们来先把这个做一下,首先。先把这个7BOARD,呃切board它的行和列写进去,这是行,这是它的列,我们先把这个行和列呢,标记成是这就代表这这个是我们的这这一步走的明白,然后呢,我们把这个VZT的。把这个当前这个位置。标记成已经访问过对不对?X加我们的column。大家看这个地方,能理解老师在在写什么吗?同学们想我们这个VT的,它是一个一位数组。
06:04
它是一个一位数组,那么我们在计算这一个是否被访问,实际上是用它的这一个行乘以这个X,再加这个column。这个X是它的列数嘛,你比如说打个比方,比如这个马儿呢,是在这一步,你们算一下是跟我的算法对不对,这是第几,如果是这一步的话,同学们看。我们X是等于八,呃,是等于八的,没有问题吧。没有问题吧,好呃,然后然后我们这一个。Co就是我们看这个算法啊,就是RA乘以X,那我们算一算对不对,RA呢?甲RA是第几行,第几行呢,数一数。01234号第四没问题吧,就是验证我们这个算法是正确的,4X是等于八。
07:00
那现在考了呢?看了等于几啊,是不是按照我们这个图形来看的话,应该是012344,好,我们看看它现在是第几个位置,对不对,那就应该等于四乘以八再加一个四,那应该是第几个元素呢?就是三十三十二加四三十六。大家看,如果按照我们这个VZT的一位速度来讲,当前这个马儿是不是属于我们的。这个第36个位置呢,我们来算哎。看看啊若若是第第几行。好,我我们看看对不对,这个算法还得验一下啊验一下。印象。啊,这是。一个八。这是第二个八。这是第三一个八,第四一个吧,那也就是现在把这个数完,其实已经是四乘以八了,没问题吧,这等于32。
08:06
是不是32,再加上我们这一个列,现在是四。四的话就是,呃。36,那同学们看,它其实是第几个位置呢?它其实是第几个位置,其实它是第37个位置。这个大家能理解吗?因为你上面32了,那三十三十二的话,再数32 33 34 35 36 37,其实它应该是37个位置。但是他虽然是37位置,但是我们这个一位数组也是从零开始标号的,所以说31还是要减一才是,我们这个马儿当前真实的位置就应该是36,这个算法是正确的。没问题吧,同学们,这点大家应该很好理解哈。我就不说那么多了,好吗,好的。那明白这个算法没有问题,过后呢,我们接着往下走,就是把这个标记为已访问标记该位置,该位置已经访问。
09:06
能能理解哈,紧接着现在呢,就要开始获取追听这句话。获取当前位置可以走的下。你下一个位置的集合,就是我们刚刚写的r list这个方法,因为我这步已经走了,是不是我应该走下一步了,但是下一个位下一个位置它是一个集合,所以说我们要便利,它还记得吧。是不是这个地方我已经写清楚了,把当前位置设置为已访问,根据当前位置记录满儿还能走的位置,好,这个刚才已经讲过了,我就不啰嗦了,直接写了啊,所以你看思路分析它是蛮重要的,Next,那你当前位置是哪一个位置呢?是不是你当前这个位置,把这个point给我传进去,你这个point就是你的列。
10:01
然后是若因为我在我们这个point他传的时候,它在取的时候,这个X呢代表它的列,所以说我传的也是列,这个要有个对应关系,不要写错了啊同学们。好,拿到这个东西过后,我们得到了一个集合,这个集合呢,我们取个名字,我们也取个名字,就叫吧。OK,那相当于说我现在获取到当前位置,可以走到下一个位置的集合了,没有任何问题。没问题,现在呢,我们要开始便利了,是不是?刚才老师讲过,我们要遍历这个our list的所有的位置,看看哪个可以走,如果走不通,走得通就继续,走不通就回溯好这段代码,看看怎么写,嗯。我写上啊,便利我们的。那你便利肯定是个外循环嘛。好,那只要不等于空是吧,它只要不等于空,那说明还没有遍历完。
11:02
没有遍历完,我们就一直去遍历,怎么遍历呢?先取出remove一个,把谁remove出来,把你当前这个取出来,听我讲啊,同学们。那现在你取到一个什么呢?诶取到一个屁了。就取到一个点,这个点呢,就是你下一步可以去走的点,是不是又传给他就可以了。是不是就是取出,取出一个可以走的位置。那你可以走的这个位置就是下一个位置嘛,取出一个下,取出下一个吧。下一个可以走的位置,我从这个集合里面取出来的。那取出来以后呢,诶,我得判断一下,你现在是否已经访问过了,判断判断该点,该点是否已经最近啊是否。是否OK,已经已已经放。
12:02
访问过,那你怎么知道他是否访问过,是不是我们这个V的里面是默认是boss,只有维two才代表已经访问过,那么写下if。V的V的,那么这个里面的下标应该什么呢?是不是就是个P。点你看你原先是行嘛,那行就是X嘛,再乘以。这个大写的X再加上p.Y是不是就呃P点。X对X代表列的啊,如果这个呢,它等于增。是不是这个等于帧,我们就不去做了?如果它不等于真,说明没有访问过。这个大家知道吗?说明没有访问过。说明还没有访问过这个能理解吧,大家有没有发现我这个px.p.X乘以X加上p.X跟我们上面去给它制成真或者假的算法一样,这个RA就是p.X这个column也是p.X吗?
13:07
这个没问题吧。这个没问题,诶那就不对,绕那个是Y啊,不好意思啊,那我我分析错了,这样才对吧,我这说的是一回事,他不小心写错了啊,这个绕是p.Y就代表它的行呃。Column呢,就是p.X这下就没问题了吧?没问题啊,说明没有访问过,我们就继续访问,那么继续访问的话呢,其实很简单,就是一个便利啊,就是我们一个递归,把切实放进去,再把这个新的RA放进去,新的是不是就p.Y。新的行,呃新的呃新的这个是行新的列。新的列是哪一个呢?好,同学们,新的列就应该是P点什么呀,同学们p.X那step就应该是加一步了,能理解不?
14:01
很好理解是吧,这段代码就写完了,核心代码就写完了。不难吧,其实一点都不难是不是?那这个核心代码写完过后,我们是不是还有一个动作要去完成,哪一个还记得吗?就是你你整个这进行整个这个while循环过后,其实它是一个递归回溯的过程。第一个回溯过程,那么大家想一想,就是你敢保证,你敢保证你整个这个。马踏棋盘就一定能完成吗?他不一定,对不对,所以说我们还涉及到一个问题,就是老师在第四步分析的判断,马儿是否完成了这个任务。那么如果没有完成呢?就把它置零就完了,那我把这句话写写到这来。那你怎么知道这个马儿有没有完成任务呢?非常的简单,一句话就可以搞定了。来,写个一。如果我们这个step。如果我们这个step干什么呀?如果我们这个step小于X乘以Y。
15:04
哎哎,X乘以Y应该是多少?是不是64啊。因为你八乘八嘛,我们是八乘八,那如果你的这个整的你进来过后,这这个步骤现在还小于这个64,说明你现在还没有达到,还没有走完。是不是如果没有走完的情况下,并且还要加一个判断,你的finish还没结束就finish呢?也是为假的情况下,两个条件同时满足说明什么呢?好,说明这个任务还没有完成。是不是就这两个条件满足的话,说明你这个任务还没有完成,没有完成的话,那没什么可说的,我们就把这个字字零确实。Ch Bo的哪一个位置呢?OK,就是它的弱,它当前这个,还有它的这一个列column。干什么呢?字为零就可以了。
16:00
好注意力。以后还有一点要把这一点。重新自为哪一点呢?就是同学们看到的原先这个位置,你原先认为它是可以访问成功的,但实际上呢,并没有访问成功,就形成一个回溯。把它干什么呢?字为。这个是不是有点像我们以前小老鼠找迷宫那种感觉,就说你假定这点是可以。走通的,并且标准出了,但是呢,因为种种原因发现并没有完成,所以说就进行一个回溯,把它重新再置为force。再注意方式,好,呃,那么这个代码写完以后。还有一种可能性,就是他满足了。如果说如果说他们就是step,它是大于等于X乘以Y了。并且呢,还满足这个分为真了,那这个时候我们就非常幸运,就把这个finish呢,再把它置为一个帧就可以了。代码就完成,那么我给大家再写一下这点这个条件成立的情况啊。
17:05
注意听,注意听,我做一个说明。说明什么呢?就是下面这两种情况。小于。小于X1Y,它这个条件成立是有两种情况的。对,听我说,就是内部小于成立。成立的情况有两种,那两种呢,第一种。第一种就是棋盘,棋盘目前到目前为止,到目前为止什么呀,仍然仍然。而仍然,仍然没有走完。说说你。小于X,还有还有一种可能性。还有一种可能是什么呢?就是你现在棋盘已经走完了,但是在属于一个回溯过程中,就棋盘呢,棋盘。
18:05
棋盘处于处于一个回溯,回溯过程。对吧,所以说这两种情况呢,我们都可以把它进行一个处理。好同学们,那代码呢,咱们就写这个核心代码,就写完了,我们来把它进行一个试用,看看我们这个代码是否能够真正的工作,就是这一段核心代码是否能够工作。其实也并不是很难,就是把老师说这个思路捋了一遍,仅此而已。
我来说两句