00:00
那今天我们看一下这个第12题矩阵中的路径,那这道题呢。它是一个DFS的问题,是一个深度优先。它是一个任意起点。给定一个矩阵以及一个字符串。看这个矩阵中是否可以有正好能通过。各种上下左右便利的方式。能够复现这个轴圈,也就是说,比如说以B为起点。它的组串是BFCE。那就上下左右的方式去便利出来。在这个矩阵中。那。要注意的一个要求,就是说这个通过的这个举证节点,它是不可以在。通过一遍了。就是用一个标识位去记录一下通过的节点。那我们就是用这种DFS回溯的方法去求解这个。
01:01
问题。从一个节点上下左右的去便利。那我们看一下这道题怎么做。嗯。我先进贡一下。啊,首先他给的这个是一个。第一个参数是一个字符串啊,是一个那个。字符数组。但是我们要用这种矩阵的方式去解决的话,先给他。呃,创建一个支付矩阵吧。会方便一点。单独去扭一下,它这个后面的长度跟宽度是给的,那我们就直接用它的已知条件。现在有了这个矩阵,然后。
02:02
就把他的。所有的值从这个字符数组里面去给提取出来。从这个字符数组提取的话,嗯,直接在这上面再加个条件。他这个。用一个key吧,嗯,关键字它是从零开始的。
03:00
嗯,写在这里面可能不太明显,单独在外面写一下。那我们每次要给这个数组赋值的时候。开合器。也就是应该付给。从这个。原本给的这个字符数组里面提取DK元素,它每次要加加。然后这样的话形成了一个矩阵,当然可以把这个方法提取出来,就提取成一个方法啊,但是我们在这里先不提取。那继续往下的话,先有了这个数组。还是要进行。直接直接拷贝上面的东西吗。还是要用用两层for循环的。
04:02
现在有了这个发循环。要做的就是一个DFS的便利。神说他如果。通过这DFS。可以找到整个路径的话,那就直接返回。错,如果找不到的话,就返回false。他这个第三个参数,我们给一个是一个。我要下标。他从零开始。我们找不路径的这个。内家人内置。那后面这两个节点呢,是。我们当前这个I和G的值。就是说如果他找到,那我们就返回这个处。他如果找不到。那我们再追问边,应该是返回这个force。
05:02
然后现在需要去实现一下这个DFS方法。一个私有的返回word类型的。这样一个方法。嗯,直接写一下这个条件吧。先是一个数组,这是一个,也是一个支字符数组的字符串的那个。给的路径。然后。Index。再者就是它当前的这个坐标值XY会比较好一些,那么这里写XY。那首先呢,这个他的边界条件就是一定要在合理范围之内的。然后他这个范围,嗯。
06:02
就是先。先比较范围,然后再比较值。因为他这个我这一晚很多次实验。他如果不这样比较,其实会出错的。那它这个范围的话。就要满足。他如果说超出它的横坐标或者是纵坐标。那就是X横坐标。它如果。小于零。或者是。他的横坐标。大于等于。我们这个数组的。长度。
07:02
就会出现问题。或者是它的纵坐标如果小于零。或者是。纵坐标大于等于零。整个宿组。就加个零,它的长度。最后我们来比较一下值。他如果给了这个数组当前坐标点的这个值。IG。他如果不等于我们。当前已经下标便利掉,便利到了这个。Str的。这个值如果是不匹配的话,就返回false,停止这个向下搜索的电历。那就是这个index。好,这种情况下无法回fo。另外一种情况下,它是返回处的。
08:02
那这种情况就是。当我们。这个长度。他当前这个index。它的下标边列的长度已经等于我们这个。嗯,Str给定的这个路径的长度。单数啊,这个地方需要减个一,因为它是从零开始的嘛。然后这个时候返回我处。这个两个for判断的时候,顺序不可以反,因为他要先符合这个范围条件才能做这个长判断。如果反了,会出现一些特殊情况。现在呢,我们要处理的就是这个。记录当前的这个。字符值。Temper。一会儿需要给他再还回去,因为要做一个标记点嘛。
09:01
所以现在要记录一下当前这个主要点IG的一个值。然后这个时候把这个当前这个IG的值变成一个星号,防止它重复遍历。这个时候呢?给他。嗯,先这说。先给他附上这个,就在这个DFS之前和之后改变这个主要点的这个。支付值,这个就是tap还回来。这时候需要有个返回值啊。Return。但是现在这个RSE没有,那我们就需要这个。
10:04
JS接收这个r fe。他这个需要考虑几种情况,上下只有四种情况。那既然是这种情况的话,就需要哪个写一下。首先他这边已经有了这个。B。再加上我们的str路径。以及我们每次这个路径的时长都要加一的。另YX。上下左右,先来上。OK,这样就先解决完一个。但是。之前测试的时候,这地方经常会出现一些奇怪的问题,但是后来又变好了。大家这个地方需要小心一下。
11:04
刚刚那个下也下好了。嗯,然后现在开始左边右。这是错。其实有。OK。这样的话就。已经完成了啊,这地方爆红是因为我们这个里面实际上没有引入这个I跟J啊,我们用的是XY,所以这个地方需要重新。改一下。OK。这样看着没什么问题。我来收拾一下。
我来说两句