379_尚硅谷_Go核心编程_数据结构和算法-迷宫回溯问题(2).avi原创

那么现在呢，我们已经已然有了这个地图了，那下一步我们就开始写这个函数来完成它，那现在呢，老师写一个函数。好，我来写一个函数。编写一个函数，完成完成小老鼠啊，我们认为这个，呃，不是不是不是小老鼠老鼠老鼠着迷啊，找出路。走。找路好，那这个代码应该怎么写呢？怎么写呢？我们来分析一下，首先你让这个小老鼠要去找迷宫，你首先得把地图给我。对，你把地图给我，而且这个地图呢，应该是大家都指向同一个地图。对，你在找的时候肯定要要指向同一个地图，所以说我写一个函数叫fun。然后呢，我就写个叫sideway啊，Sideway就是呃，或者叫findway都可以啊，啊findway也可以，我就叫sideway了，就是设置设置一个点嘛，标标标标线嘛，然后呢，首先把地图给我，我把这个地图地图先拿到my map。

那这个时候这个地图呢，它应该是一个引用型的给我传进来啊，不要每次都给一个新的地图复制一份，那就完蛋了啊啊印子，那么还有需要什么信息呢？你得告诉我你是从哪个地方去找。所以说你需要给我两个坐标，对，你得给我两个坐标，那么I一个坐标。好的I。In go。高，也来一个印子。好，我先说一下这个这个含义啊，这个代码不多，但是理解起来有点难度，这个就是代表这个地图。就是每一次呢，把这个地图给我。这就是地图，地图呢是同一个，始终是同一个啊，一定要保证始终是同一个地图，在同一个地图上找，要保证。保证是同一个地图啊地图，因此呢，我这里使用是引用。

因此，因此使用引用。引用。好，引用。那么这个I和节表示什么呢？I和节表示当前是在对哪一个点或者对哪一个格子进行这个测试表示。表示对对地图的地图的哪个点哪个点。哪个点。进行测试。好了。那现在代码就要开始写了，现在代码就要开始写了，那么记住我刚才的规则，记住我刚才的规则，来上来第一句话。嗯，我们现在首先判断啊，因为我原先讲过，就是咱们在进行递归的时候呢，必须要分析出来什么时候。算是找到了，或者说算是找不到。对吧，那么首先呢，我们先做这样子，就我们分析出来什么时候算是。

找到了呢，大家可以想象，因为我刚才讲过二代表一个通路，大家想象如果在整个这个找茬的过程中，我们发现这个点。这个点就是现在我用箭头标这个点等于二了。那你一定找到通路了。肯定这样子的嘛，因为你不管怎么着，你你这个都飙到二了，那肯定就找到通路，那该走了呀，你别再找了，所以说我们已经分析出来找到的这个关系了。哎，这点是很重要的了，要分析出分析出什么情况下。什么情况下？就找到出路了，就找到出路。对，那么我们刚才分析出来这个结果呢，是这样子的，就是如果我们的map。它的这个点，这个点其实就是六五这个点。大家看一下是不是六和五，如果它等于二就可以了，为什么是六和五呢？大家看一下啊，你看吗？这这这一行就是第七行嘛，第七行但是从下边来说是六嘛，这边是啊，这边是第六第六列，第六列呢，从这个它的下边来说是杠是五嘛，所以说六五，如果是六，五等于二就找到了，所以说上来第一句话，如果，如果什么呢？这个地方我们会返回一个布尔值，代表找到成功。

好，那我现在开始写了。如果卖。六。五等于二。好，我们认为找到了，但是为什么我这是二啊，因为我刚才已经把这个把我的规则说清楚了的，如果我上面突然写个二，大家可能不理解为什么，因为我的我我定的规则是这样子的，如果你们定的规则不是说，而二表示通路，你是五表示通路，那就是五，好，那么就说找到了吗？那就怎么呢？就说你可以打出一句话。但你也可以不打，我就直接就说明找到了，别再玩了。就返回一个针。

就成功了，就就成功找到了，就像战队，我我已经OK了，我已经OK了，好如果说。注意，同学们看。Else。如果你这个map，就说你这个my map65，它不等于二，说明你还要继续找。说明要继续。继续找。那么问题又来了，同学们分析一下啊。那你找的时候，你在找的时候，你得分析出来它是不是一堵墙。所以说也就是说你在探，因为我们这个目标是探测这个点，对这个点进行探测，如果本身这个点它都等于一堵墙了。你还探个啥呀，他本身一进去它是个一，你能你能探吗？所以说你要找的时候，你要先判断它是不是可以探测。说老师这个题目看起来有点突然有点懵的感觉啊，但是很正常，你慢慢就好了，你把代码写完啊看，就说你你要找的，你首先判断你能不能进行探测，如果前面都是一堵墙，你就没法探，所以说呢，你先判断，如果这个I。

这个勾它如果等于零，你才能看这个意思，就是说什么意思呢，就是说。如果该点，如就是说你你得分析出来，如果这个点这个点。是。可以探测的。探测。而且还没有探测过。对吧，如如果是可以探测的，你就看，那么如果它不等于零，你你举举个例子啊，打个比方，同学们看。比如说我们上来过后就直接往上探测，打个比方啊，我们做一个最极端的案例，就这个小球他在这儿，然后他直接往上一一顶。他发现，诶，这是一堵墙，那就。那就别看了，因为这这堵墙不能出这个图，不能出这堵墙，所以说你在这个情况下呢，如果不等于零，它就一定等于一，就是针对针对刚刚去探测的时候，他们要么等于零，要么等于一嘛，就是针对这个原始的图，所以这个地方呢，说明它是一堵墙。

说明这个点，这个点。不能看。不能探测。不能探测，呃，为什么不能探测呢？因为它是等于一的，因为是一堵墙，因为唯一。为四四强。啊，既然是强的话呢，就直接告诉他不能走，直接一个force，就我告诉你走不了这这事。好，里面最麻烦了，因为里面呢，它涉及到一种关系，就说你怎么探测的问题。首先，同学们啊。注意听我的solo，因为现在这个这个时点是可以探测的。那么所以说我的思路这样子的，我先把它置为二，我认为它，我认为它可以通啊，就是说我我的思路这样子的，我先认为我假设，注意这是假设啊，假设这一点是通路。

但是实际实际上是不通突，我不知道，我必须要通过这个探测我才能知道，所以说假设my map这点就是假设这个点。这个点是可以通的，是可以通的。呃，就好像因为你你你不你你只有只有假设它是通，你才能反推它不通，所以说假设它是通的话呢，我就先将其置为二。这边有很多概念，还有那个思维在里边啊，我是我是我假设它会通，但是实际上是不通，不知道我要我要真正探测啊，但是到底能不能通，我要我要我要玩一把，但是实际上啊，但是通不通，是否真正的通啊，但是要需要探测，但是。啊，但是。但是需要需要测探视探测，那么假设呢，那我开始怎么探测呢？好，我这样探测了啊。

我先根据我的这个规则，我的规则是先上。我的，因为大家想这个策略自然就出来了，你想一想。你你既然要探测你一个点有五个，你你在一个一个点，你你可以向上走，可以向左走，可以向下走，可以说肯定涉及到一个策略。那你必须得告诉你，你先往哪儿走啊？当然有些同学可能说了，老师我也不知道，我那就随便选一个，那就意味着这一个点本这一个点针对这一个点就有好好几种选项了。它至少你看呢，就是上下左右你进行一个组合。那这那这顺序就好多了，可以先上再下，也可以先上再做，那这个就很多很多了，那么我就假设我的这个是这样子的啊，我假设这个，那我现在开始看了。如果追听。Sway。好，我把麦传给你，让你去做一个测试。

那么此时此刻向上探测。怎么样才体现出向上看呢？显然，我只需要把这个I。减一下一就可以了。因为减一就是相当于这个点往上走了嘛，那要行嘛，所以说向上走的话是I。减掉一个一高不变，如果这条路通了。因为我从这个点往下走。注意啊，他会往下走的时候，他会不停的往下走哦，假设这条路通了，那我很高兴，说明成功了。因为这条路就说从这个点往下往上走，它又涉及到不同的逻辑，那反正不管怎么样，你最后总是有个结果嘛，到底能不能通，你你得告诉我好，如果通了，我就一个处。说明这个OK。就针对往上走，这条线是能够往下一直走的，但是能不能走不知道，所以说我认为这个就做了一个判断，如果它返回一个针。

至于它这个真是哪一层返回来不知道啊，同学们，这点大家要理解啊，就说它到底是不是这个最终这个最终这个set位到底是哪一个，哪一个递归返回来的，因为它是不停的往下递归递归递归，他肯定要把这条路整个走通了，它是一个return return出出出出。返回来的，你不要理解成只有一层哦。这点不好理解。同学们。你要理解到，你要你要看到这个代码，你要理解到他在已经在不停的往下看了。也就说这条路一直是通的，它就会不停的返回，出出出出出，好这呢大家要理解，然后这个是向上，这个是向上。这个有点不好理解，说实话，然后呢，那如果向上走不通怎么办呢？因为你这个将来也有可能是走不通的。就是你从这边往往上走，结果没有通，没有通的话呢，那我就尝试着往下走。

因为上上面往上走不通了，那就往下走，往下走呢，大家想想这个逻辑应该是什么呢？就是else if set为my map，然后向下走上向下走的话，这个地方就应该是。加一。好，如果向向下走走通了，那我很高兴，我就一个。Ta一个处。就说就别再走了啊，这往下走是这条路一直往下走是可以成功的。向下走。同学们注意啊，它往下走到到下一层里面，又又是又又是按照这个逻辑来走的，不是它一直往下走哦。啊，然后这个向下走，紧接着a if，如果向下这个是走不通的，就是走不通的呢，那么我就向左探测。向左探测，向左探测呢？那同学们想想，向左探测的话，我们要改变的应该是哪一个值呢？I不用变化。

勾就说么，这个节呢向左嘛，那肯定就是减一。好，如果这个向左走能通也很高兴左。注意听啊左，那么这个时候呢，我也给他返回一个处，说明向左走。最后是成功了，但是他这里面只有一个方向能够成功，因为是我用的是一伏L11伏啊，只要进到这里面成功了，只要这面成功了，他就就不会再去探测，只有他这个不成功才去向下走，向下走不成功才会向左走，大家看到这个逻辑啊，这个代码一点都不能错。错了就完蛋。所以这个为什么用的是l if，那么这个向左走，如果也不通的话，那么我们就尝试着向右走。好，向右走的话呢，这个逻辑就应该是向右走I不变，这个节呢加一。

好，然后这个地方向左走。啊，这个是向右走了啊，向右走。非常好，向右走，那么如果这个向右走也能向右走能成功，我们就返回一个针。它每一层在不停往上返，返回这个针了，当然还有一种可能性，就是上下左右都不通。如果都不通，同学们要注意啊，这一点就很重要了。这个逻辑。如果都没有走通，说明这是一条死路。就从这个点往上走，它是死路，就从这个点本身，当前这个点往上走，走不通，上下，上下都左右都不通，那就你可以想象到你好像在一个点把你围死了。就说。就说你上下走又通不通，你当前这个，你从当前这个点，注意啊，它是在当前这个点往上走，走不通，那说明你这这个上下走又都不通，是条死路。就说你现在已经被围起来，感觉好像被围起来了，好，这个就是死路，就是这个点是死了死路，那么一旦是死路，同学们应该马上把这个重新置为。

三也就是说。他还在这一层啊，就说你你这个假设是错的。你这个假设是错的，假设一旦是错呢，我就把它制成一个三，并且返回一个false。好。干嘛就写完了？代码就写完了，说可能同学们待会这样子啊，如果大家理解不了的话呢，我待会儿就是找一个特别简单的地图，大家就很好理解，来吧，我们先来看看这个效果对不对，再把这个理解一下啊，我是怎么走的，把这个逻辑再捋一捋，我上来过后。先判断你现在是不是已经找到通路了，如果找到通路就不要玩了，赶紧走人。因为你你再往下走就就没有意义了，好如果六和五还不等于二，说明没有找到通路，没有找到通路的话呢，我就判断你这个点能不能探测，如果等于零，代表这个点是可以探测的，如果不等于零，在初始情况下，它只能等于一，就是一条，就是一栋一堵墙一堵墙的话，就不要再探。

就碰到墙了，你还探测什么呢？就直接返回方式，在这个等于零这个地方呢，我先假设你是可以通的，但是这个假设是不是真的不知道，所以说我就尝试着用我的一个策略，先上上向上走。向上走，如果走得通，他在那个点继续往按这个逻辑走啊，注意听不不是向上走走不通，他就他就这个向上走，走得通，他到下一个点继续采用这个上下左右，继续往往往那个走，明白我的意思吧，不是它不是说不是说在同一个点，在同一个点进行这个上下左右，而是它只要走通了，它在下个点又上下左右，如果那个又走通，有一条线走通了，就向下左左右，好注意理解这个意思啊，好，那么如果假设你这个点上下走都走不通，那么就是一堵墙啊，是死路，好，代码写完我们来玩一把。

到底能不能成功呢？我们来玩一把测试。使用测试一下。呃，那么现在很简单哈，同学们，我只需要set位。赛特way。然后呢，我把一个地图传给他，这个地图呢，就是my map，但传的时候呢，咱们需要传的是一个可爱的地址，然后呢，我从哪个地方开始进行探测呢，显然是一一这个点。因为呃，大家看到我的墙啊，呃，这个是就是这个点，就这个点是我们的出发点。显然是一一好，这个点是我们的出发点，一好现在呢就可以看，看完了过后我们输出地图。看看到底有没有通。好，这个是探测完毕的地图。好，这个是这个叫叫什么呢？探测完毕的。

探测完毕的。好，我们看看这个地图现在能否能否通啊，不知道，我试一下。早。好，同学们看我这个地方是有问题的啊，我这个代码是有问题的，全部都制成二肯定是不对的，肯定是不对的，我们看看哪个地方出了问题了，我们来分析一下，来分析吧，那大家看到我们现在这个地图其实他走通了。它走通了，但是这个大家看到是走通了，它应该是这样走的，向这走，然后回到这又上走，像这样，像这样，像这样。看到没有，就相当于这样不停的走，但是这个策略不好，我们换一个策略，我们这样走，我们换一个下右上左。那为什么下游上者又好了呢？来，我们来换一个策略。我们尝试着换另外一个策略啊。换一个。一个策略。这个策略呢，我们改成下右上左。

下游上次我们先这样子说啊，我们先不用，我们先不要不要让这个小小老鼠去探测，我们自己人为的分析一下，看看它应该是什么路径啊，我现在没有设障碍。我先比如说下右上左来我们分析下右上左啊，下右上左，我把这个粘过来，因为这个地方人容易呃，容易蒙圈，所以说我把这个粘过来，把地图也粘过来啊，我们来分析一下，注意听，同学们注意听啊。啊，现在我的地图呢，是这样子的。好呃，这两个圈圈，这两个先要要不先把这个也加，也加上也可以啊，也加上也可以，好，我们现在开始探测了。这有一个小的指针。好，来了地图小小小老鼠从这地方开始来玩了。小路，他先向下走。哎，向下走下到了这一点，到了这点是不是它又相当于继续采用这个下右上左的策略。

这点大家一定要明白，下下手是不是堵住了呀？哎，堵住了没有关系，呃，那我这样子，我我把这两个点也加上吧，好不好，我把这两个点也加上，把这个墙加上，不然的话，我分析起来大家可能听的有有点模糊，我也不太容易讲通，我把这两个点加上，把这两个强加上的话，大家想想应该怎么加呀，是不是，呃，三一和三二对吧，三一和三二来把这两个，把这两堵墙加加进去。把这堵墙加进去，加一个三一和三二，各位同学啊，不着急，我们再给他加点东西。Map。My map一个三。一个一给他一一个强。还有呢，三二。给大家一个钱，好，我们先来看一下目前这个地图是什么样子的，我先把它看一下，跟我想的是不是一样的啊，先看地图。好，同学们可以看到现在地图呢，跟我们想的一样，这有这有两个两两两个一，两个一就代表强了嘛，好，我们现在接着来分析。

好，那现在到这儿来了啊，现在小小老鼠从这先置为二，先置为一个二往下走。先置为二，发现这个二呢，呃，往下再再往下走，走不通，走不通他还不会马上马上把它置为三，因为它还要相当于回到回到这个点了，回到这个点呢，他又向这个右，因为下走不通嘛，他又向右走，哎，他发现右可以走通，非常高兴，但是到了这一点过后呢，他仍然采用下右向左的策略，明白这意思吧，好，他继续往下走，他发现这个地方仍然是一堵墙，于是他又回溯到这点啊，然回溯到这点，他又向右走，他发现这个墙走得通。是不是到了这一点，是不是他又向下走，诶走通了，向下走，哎又走通了，向下走还走通了，向下走还走通了，非常高兴。那当然，他高不高兴我们不知道啊，然后呢，接着他到这点，他又向下走，他说哎，怎么又是一堵墙啊，于是他又回到这点，接着往往往这边又走，走通了，走到这一点，他又向下走。

现在他走不通，他又回来了，他又回来，哎，他这怎么办呢，就想走好，所以说这个点我们应该清楚的看到，他是这样子的。这条线。大家理解一下啊，就这条线，整个这个二应该是这样制的，走走就是这样子的一条线，我给他画一下。好，是这条线我们看对不对，我们看看跟老师分析的是否一样，好我把它打开。我把它打开，那各位朋友我把它打开。打开购物呢，我们来玩一把。找代码。做代码。还是有问题。为什么这个地方还是有问题呢？好，我们再看代，这就是我代码真的有问题了，我们看一下代码哪里有问题啊，代码真的是有问题，我们看哪里出了问题了。Map等于二，那那个思路是没问题的啊，就是代码肯定哪个地方需要再调整一下诶。

再调整一下。好呃，那这样子啊，我们现在呢，把这个策略也做相应的改变，因为我还是上下左右，我把它改成这个下右上左来走下。那我改了啊，向下走。没问题。下右。又是这个逻辑。又是这个逻辑，把这个改一下，就是ii不动。I不动，I不动的话是结加一对结加一没问题，这个就就改成这个，这个是下了啊，我们把这个调调整一下下。右。You。有好，呃，然后是上上。啊上的话呢，就是把这个结减掉一个一啊ii减掉一个一，然后节不变，对节不变。啊，然后最后一个就是左边。左边。啊，左边呢啊就是I它是不用变化的，I是不用变化的，把这个节呢，诶对减一。

节俭的一个意义，好，同学们，现在这个策略我就变化了啊，我们再来跑一下。再来跑一下走。好，同学们，这次呢，跟我们想的就完全一样了，大家可以看到。好，跟我们分析的是完全一样的，那为什么刚才是那样一个路径呢？这样一个路径就是根本原因就是，呃，就是因为我们那个策略采用的不好，那个策略是你，你可以看到它是一个什么策略，对吧？他显然如果你按照这个策略分析出来应该也是一样的，好，我们再来做一个情况。就说有这么一个情况，他就是找不到我们这个代码有没有问题。就说假设我是一个很很恶心的111个地图，就是把这彻底的堵死。他这个小老鼠，它能不能死在这里面呢？就是说我把这一方设成一个挡板，把这样设成一个挡板。那这个小老鼠就。他们要一车全部死在这里面，他会不会？

蒙圈呢，好，我们来看看这个地图会出现一个什么情况啊，好，我把它堵死啊，同学们，我把它堵死，那这个时候呢，我就需要在二。是112和二二再加两个点对不对？好，我们看看代码有没有问题，好来把它读死。好一二。一二和二二好，我们先来看地图对不对，先不着急先看地图对不对啊朋友们。先把地图给大家伙输出来。输出来。好可以看到，嗯，现在呢，地图的的确确这个地方是一个。框死的东西就彻底堵死了，那么现在我们来跑一跑，看代码能不能跑起来。好，同学们，现在呢，我们来执行一下代码，看有没有出现一个死循环。还可以，没有毛病，他退出来了，那这个时候他是怎么退出来的，从哪退出来的，大家可以想想。

大家想想，你看他上来过后，经过他的分析，他他他很遗憾的说，这是条死路，这是条死路，然后他很绝望，就他就不玩了。那这个时候它是从哪推出来的，大家想一想代码。大家想想，显然他不可能是从这儿退的。因为他不可能在这，那么就意味着它应该是从哪推的呢？它整个要么是这个代码，因为你的代码这个if else else进来过后，它不等于它，它只能是在这，它就是在这地方不停的反退，Return，但不停的回溯吗。变成全部都找不到。好，最后就彻底完蛋了，也有可能是从这儿退出去的，就是智为三，退自成三，那么大家可以去把这个代码想一想啊想一想。好，这个是我们的这段代码的一个，呃，代码一个分析，我把它进行一个板书，板书完了过后呢，待会我出一个思考题，大家想一想，好，好，我把这个板书一下，同学们。好的，我把它反述一下，那具体来说这个代码呢。

我板述一下。A阐述一下。好，刚才我们写的这个代码。还有分析。我们就放到这里，老师呢就不啰嗦了，直接把这个东西放这就行了。好的。然后我给大家留一个思考题，我给大家留一个思考题，这个思考题同学们想一想怎么做啊，我留一个课后思考题。课后思考题，这个思考题呢，我希望同学们在老师这个代码基础上能够把它搞定。这样大家。有一个有一个有一个智商的增长，就是说大家看到啊。我们。我们刚才已经分析出来就是这个策略。对，我们将来这个路径有。很大的影响。就是你不同的策略，最后找到这个路径肯定是不一样的。那么现在我要我要问大家就说你如何找到最短路径，你看刚才我们那个不好的处理，你会发现它是这样走的。

结果我们改变了一个策略，改成下右上左，哎，这个路径就很顺畅。但是迷宫大了，我们将来我们将来这个这个挡板很多的情况下。那么你怎么用程序找到哪一条路是最棒的一条路？那这个就有很多现实的意义了。比如说同学们将来。你们在程序里面，别人。比你的项目经理给你出了一个，说我们现在要写一个地图，比如说写一个地图吧，说我这有很多公交站。那么公交站呢，由这个A站到达这个，比如到达到达一个叫K站，我们这有很多很多公交站的节点。那么请你设计怎么走是最短的？你你不可能每次都都用人的脑袋去想啊，你说哎，我数一数。那不行吧，那你就想，诶，你能不能把它构建成一个。

类似于这样一个逻辑，然后呢，找到最短路径，说白了就是想办法给我找到最短路径，这是同学们做一个课后题去思考的，就是你怎么找到最短路径。最笨的办法。各位最笨最笨的办法，你想一想怎么做？穷举法最笨。我把所有的路径全部走一圈。然后呢，我把路径放在一个map里面去，最后看哪个map的长度最短。这最笨的办法嘛，对不对，但是说方法虽然很笨。但是他毕竟还是把问题解决了，因为如果你要涉及到优化，他设计的东西就很多了，就数学上很多这个算法东西，你先用一个最笨的办法把它解决了，至少你跟别人说，诶，我有思路优化的地方呢，大家可以再去看，去看一下这个数学相关的一些这个这个公式，数学公式去进行这个解决好了，这个呢，我就留一个思考点留给大家啊，希望同学们这个比如说。

咱们班有同学能够提出他的一个解决方案。好的，同学们，那关于这个案例呢，我们先给大家讲解到这里，同学们。