php - 不懂算法的人的模式匹配 - 在网格中找到相邻的 X

Question

我想知道解决需要在提供的网格中找到相邻(水平、垂直、对角线)X 的问题的最佳方法是什么。

我想知道什么是递归方式，什么是非递归方式。我尝试了一种检查每一列的递归方法，然后迭代行 - 这在一个方向上给了我 X - 我应该为其他方向编写单独的递归函数吗？

示例网格:

XXX0X 0000X 00X00 XXXX0 0000X

输出应该是:

• (0,0),(1,0),(2,0)
• (4,0),(4,1)
• (2,2),(0,3),(1,3),(2,3)(3,3)

Answer 1

您可能想查看 Flood Fill 算法。您可以在维基百科上找到它。

我认为您所描述的或多或少是这样。你所做的基本上是:

For a given position:
If it is of the desired color (in your case 'O'):
  mark it (say, re-color it to a color 'M'),
  recurse on all desirable directions (run the same algorithm
    on new positions, which are +/-1 away);
else
  do nothing.

在您的例子中，结果是标记为“M”的位置。如果您想找到其他邻接点，您可以随时重置标记为“M”的邻接点并在不同的位置开始算法。

编辑:根据您的示例，您似乎正在寻找相邻的“X”。 :)