斜向三消查找算法的原理和实现

嗨！大家好，我是小蚂蚁。

之前的文章中我们讲了三消查找算法的原理和实现，通常的三消指的是水平和竖直方向上的消除。现在我们想要做点儿新花样，想在斜方向也可以消除，那斜向的三消查找算法如何实现呢？今天就来讲一下。

斜向查找的原理

如图，黑线画出来的红色宝石满足斜方向上的三消条件，所以这些红色宝石能够消除。

斜方向分为两种，一种是从左下方向右上方倾斜，我们把它叫做“向右斜”，一种是从右下方向左上方倾斜，我们把它叫做“向左斜”。对于斜方向的查找，就是沿着两个方向查找，即“向右斜查找”和“向左斜查找”。

首先，仍然是进行一下数据抽象，构建一个由数字组成的表格，这个表格是后续的判断和计算的基础。

整个斜向查找过程是这样的：

从第一行第一列的宝石开始。

先进行“右斜”查找，检查右上方的宝石是否与自己相同，如果相同就记录下来，然后继续向右上方检查，直到右上方的宝石与自己不同为止。查找完成后，统计找到的相同的宝石数量，如果大于等于 3 个，则记录这些宝石满足消除条件。

再进行“左斜”查找，检查左上方的宝石是否与自己相同，如果相同就记录下来，然后继续向左上方检查，直到左上方的宝石与自己不同为止。查找完成后，统计找到的相同的宝石数量，如果大于等于 3 个，则记录这些宝石满足消除条件。

接着检查第一行第二列的宝石。

......

直到所有的宝石检查完毕为止。

来看一下第一行第一列宝石的整个查找过程。

接着将剩下的每个宝石都进行一次斜方向的查找，所有的宝石都查找完毕后，整个查找过程就结束了。

如图，“向右斜”的查找用蓝线表示，“向左斜”的查找用绿线表示。其实，在这整个查找遍历的过程中，并不需要将表格中的每个宝石都进行一遍斜向的查找，例如在对第 1 行 1 列的宝石进行查找的过程中，已经找到了与它相同的第 2 行 2 列的，以及第 3 行 3 列的宝石。所以这两个宝石在遍历查找的过程中，就不需要再次进行检查了。

可以借助一个列表来记录那些已经检查过的，不需要再次检查的宝石。在检查之前可以先检查一下列表，如果这个宝石已经在里面了，就无需再次检查了。这样可以提升整个遍历检查的效率，即使计算机很擅长计算，我们也不要让它去做重复的无意义工作。

至于怎么找到右上方或者左上方的宝石呢？其实非常的简单，已知当前宝石的行列号，那么它右上方的宝石就是（行号+1，列号+1），左上方的宝石就是（行号+1，列号-1）。

以上就是斜向查找的理论基础了，要比水平竖直的三消查找简单很多。

斜向查找的实现

接着，来看一下在微信小游戏制作工具中的实现方式，其它游戏引擎的实现方式原理类似。

看一下斜向查找的积木逻辑。

右斜查找的函数，其中只包含一个斜方向查找的迭代函数。

接着来看一下两个一模一样的迭代函数。

除了名字不一样，所有的积木都一样。

以上就是斜向三消查找的原理和实现了，你会发现其实它跟水平竖直的三消查找都大同小异，只要理解透彻一个，其它就能够信手拈来。

这些原理往往都是一些看似很难，但是实际上并不难的东西。这里分享一点儿我自己的学习技巧，有些东西，尤其是之前从未接触过的，乍一看，完全看不懂。这时的第一反应往往是抗拒，头脑里会蹦出一个小人，不停的说：不要弄了，这个太难了，你学不会，看都看不懂，怎么学呢？

此时，我就会不停的告诉自己：看不懂很正常，那就多看几遍，使劲看，早晚能够看的懂。现实往往也是这个样子，每多看一遍似乎就能够多懂一点点，当看的遍数足够多了，这个东西就变的不再难了。另外，除了看，动手也很重要，我习惯于在纸上画，这能够帮助我更好的理顺思路，更好的理解问题。

其实不大部分学不会的东西，并不是因为它太难了，而是因为我们太懒了。

要么就一次搞明白，要么就遇到一次头疼一次。