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 是迄今为止找到的有效邻居的数量)。