c - 检查二维数组中非连续分组的更好算法

Question

我在做文字游戏。该板表示为二维 C 阵列。我填充的数组的简化版本可能看起来像这样。

[x][x][0][0][0][0][0][x][0][0][0][x][0][0][x][0][0][x][x][x][x][0][0][0][0][x][0][0]

x block 之间没有对角线连接，只有上、下、左、右。

我想要一种算法来检查是否存在两个不连续的 X 值“ block ”。给定一个特定的 2D 游戏数组，该算法将使我能够在以下两者之间做出决定:

• 是的，只有一个连续的 X block
• 不，有不止一个连续的 X block

对于上面显示的示例，我会找到“否”，因为存在不止一个连续的 X block 。

我的第一个简单想法是找到一个连续的 X block 并对这些值进行分类。由于对这个问题不重要的原因，我很容易在连续 block 的中间得到一个起点。如果我能在任何不在我的编目列表中的地方找到 X，我可以返回“否”，否则返回"is"。然而，我认为这是一种非常低效的方法。

我知道我需要触摸二维数组的每一项才能全面排除另一个连续 block 。我对找到“否”的最快方法更感兴趣。

因为数组非常小，所以我可以在没有任何实际性能问题的情况下实现我的想法。但是，我确信有一种更优雅的方法，我认为这个问题可能会引起堆栈溢出 hive 思维中一些喜欢算法的部分的兴趣。

这也可以在另一个 SO 问题或整个互联网的某个地方进行描述。也许我只是不知道用正确的方式来表达这个问题。如果你这样做，请赐教。 Best solution 还可以免费获得一份尚未完成的 iOS 文字游戏。 :-D

Answer 1

您的数组形成了一个图，您在询问该图是否有多个连通分量。执行此操作的最简单方法可能是复制数组，删除找到的第一个连通分量，然后寻找另一个 X。如果找到一个，则开始时有多个分量。

删除是图形搜索的一个很好的应用。例如，您可以这样做(在 C 中):

#define N_ROWS 4
#define N_COLS 7
typedef char WORD_BOX[N_ROWS][N_COLS];

void erase_cc(WORD_BOX box, int i, int j)
{
  if (i < 0 || j < 0 || i >= N_ROWS || j >= N_COLS || box[i][j] != 'X')
    return;
  box[i][j] = 'O';
  erase_cc(box, i - 1, j);
  erase_cc(box, i + 1, j);
  erase_cc(box, i, j - 1);
  erase_cc(box, i, j + 1);
}

int find_cc(WORD_BOX box, int *i_ret, int *j_ret)
{
  int i, j;
  for (i = 0; i < N_ROWS; i++)
    for (j = 0; j < N_COLS; j++)
      if (box[i][j] == 'X') {
        *i_ret = i;
        *j_ret = j;
        return 1;
      }
  return 0;
}


int more_than_one_cc(WORD_BOX box)
{
  int i,  j;
  WORD_BOX copy;
  memcpy(copy, box, sizeof(WORD_BOX));
  if (find_cc(copy, &i, &j)) {
    erase_cc(copy, i, j);
    return find_cc(copy, &i, &j);
  }
  return 0;
}