c - 如何在 C 中的整数数组中选择(有效)随机相邻点？

Question

假设我们有一个整数数组 (3x3)，如下所示:

+-+-+-+
| |1| |
+-+-+-+
|0|x|1|
+-+-+-+
| |0| |
+-+-+-+

上面的(0,1)设置为1，(1,0)设置为0等。

现在假设我发现自己处于 (1,1) (在 x)，对我来说最简单的方法是什么，可以得出我可以采取的所有方向(假设所有值为 0 的方向)，然后在那些选择一个？

我遇到的麻烦实际上是选择所有有效方向然后在其中进行选择之间的步骤。我可以相当容易地分别完成这两个步骤，但我没有一个将这两个步骤结合起来的优雅的解决方案。

例如我可以将每个单元格的值乘以代表 1、2、4 和 8 和/或它们的值。这将告诉我可以采取哪些方向，但如何在它们之间进行选择？另外，我可以轻松地随机化 1 到 4 之间的数字来选择方向，但如果该方向被“采用”，那么我必须再次随机化，但排除失败的方向。

有什么想法吗？

Answer 1

最快的解决方案可能是您发布的最后一个解决方案 - 随机选择方向，重复直到获得有效的方向。这最多需要四次尝试(最坏的情况是只有一个有效的邻居)。更优雅的方法是迭代所有可能的方向，在每个有效邻居处随机更新变量，例如以下伪代码:

c = 1
r = invalid
for i in neighbors:
  if (valid[i]):
    if (rand() <= 1. / c): r = i
    ++c

然后r就是答案(c是迄今为止找到的有效邻居的数量)。