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

Question

我正在做一个文字游戏。该板表示为 2D 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块之间没有对角线连接，只有上、下、左、右。

我想要一个算法来检查是否有两个不连续的 X 值“块”。这个算法，给定一个特定的 2D 游戏数组，将使我能够在：

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

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

我的第一个简单想法是找到一个连续的 X 块并将这些值编入目录。由于对这个问题不重要的原因，我很容易在一个连续块的中间找到一个起点。如果我可以在不在我的编目列表中的任何地方找到 X，我可以返回“否”，否则，“是”。然而，这让我觉得这是一种非常低效的方式。

我知道我需要触摸 2D 数组的每个项目以全面排除另一个连续块。我对找到“不”的最快方法更感兴趣。

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

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

score 2 · Accepted Answer

您的数组形成了一个图形，并且您在询问该图形是否具有多个连接组件。最简单的方法可能是复制数组，擦除找到的第一个连接组件，然后查找另一个 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;
}

score 1 · Accepted Answer

以下最优解为 O( n ) 的运行时间，不仅计算是否存在两个以上的连续序列，而且计算

返回找到的序列的确切数量（水平和垂直）
返回每个序列在水平和垂直方向上的位置和长度（对代码进行非常小的重新排列）。

您的问题的解决方案可以非常有效且简单地解决，无需使用任何类型的图论，而只需使用您对数组的了解，并利用您对它们在内存中的布局方式的了解。下面的 C 程序演示了这个原理。

static inline void TrackLength(int **hpnCountPtr, int *pSeqStart)
{
    (*((*hpnCountPtr) ? (*hpnCountPtr) : (*hpnCountPtr = pSeqStart)))++;
}

static int FindSequences(char *pcbGrid, int nWidth, int nHeight)
{
    int    nColIndex, nRowIndex, nSeqTotal;
    int   *panResult, *pnHorzSeq, *panVTable;
    int  **panVertSeqs;
    size_t nResultLen;
    char  *pcbCheckPtr;

    nResultLen = (size_t) (2 * nWidth * nHeight) * sizeof(int);
    panResult  = (int*) memset(alloca(nResultLen), 0, nResultLen);
    panVTable  = panResult + (nWidth * nHeight);

    panVertSeqs = (int**) alloca(nWidth * sizeof(int*));
    for (nColIndex = 0; nColIndex < nWidth; panVertSeqs[nColIndex++] = (int*) NULL);

    for (pcbCheckPtr = pcbGrid, nRowIndex = 0; nRowIndex < nHeight; nRowIndex++)
        for (pnHorzSeq = (int*) NULL, nColIndex = 0; nColIndex < nWidth; nColIndex++, pcbCheckPtr++)
        {
            if (*pcbCheckPtr != 'X')
            {
                pnHorzSeq = panVertSeqs[nColIndex] = (int*) NULL;
                continue;
            }

            TrackLength(&pnHorzSeq, panResult + (pcbCheckPtr - pcbGrid));
            TrackLength(panVertSeqs + nColIndex, panVTable + (pcbCheckPtr - pcbGrid));
        }

    /* Insert Debug Information Here */

    for (nSeqTotal = 0, nColIndex = nWidth * nHeight; nColIndex; nColIndex--)
        if (*panResult++ > 1)
            nSeqTotal++;

    return nSeqTotal;
}

关键在于您的要求是只需要找到水平和垂直序列，而不是对角线。作为一个 2D 数组，这意味着可以通过知道 2D 数组是简单的平坦、连续的内存块来进行巨大的优化，可以一次从头到尾遍历。

利用内存安排，可以仅使用单个计数器跟踪水平序列，该计数器针对每个连续的内存位置递增X，并且每次X遇到非时重置为零。如果在阵列的 2D 视图中每个“行”的末尾强制重置计数器，这将成功跟踪水平序列。

在跟踪水平序列的同时，我们可以同时跟踪垂直序列。但是，由于数组中列中的相邻单元格以width字节间距出现，因此我们必须保留一个计数器数组，width这些计数器在我们扫描行时跟踪行中所有可能的垂直序列，每列一个序列。

最后，我的解决方案的真正美妙之处在于计数器实际上是指向两个 2D 数组的指针（一个用于跟踪垂直序列，一个用于跟踪水平序列）。每个数组中的每个位置都代表一个序列的潜在开始，当函数完成时，每个数组将在每个位置包含从该位置开始的每个序列的长度。

下图最好地说明了这一点：

   Grid      Horizontal    Vertical
             Sequences    Sequences

....X...X.   0000100010   0000300030
.X..X...X.   0100100010   0300000000
.XXXX..XXX   0400000300   0011000201
.X.....X..   0100000100   0000000000

水平序列数组中的每个数字代表从该点开始的水平序列的长度。垂直序列的垂直序列数组也是如此。

由于程序使一个并且恰好一个传递输入数组，并且每个数组元素的处理时间是恒定的，因此该算法在 O( n ) 中运行并且对于任何大小的网格都是最佳的。

如果在下面的程序中插入上述函数：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloca.h>

#define GRID_WIDTH  18
#define GRID_HEIGHT  9

static char *s_szGrid =
    "X X X X X X X X X "
    " X X X X X X X X X"
    "X X X X X X X X X "
    " X X X X X X X X X"
    "XXX X X X X X X X "
    " X X X X X X X X X"
    "XXXXX X X X X X X "
    " X X X X X X X X X"
    "X X XXX X X X X X ";

void main(void)
{
    int nSeqTotal = FindSequences(s_szGrid, GRID_WIDTH, GRID_HEIGHT);

    printf("\nGrid has %i contiguous sequences\n", nSeqTotal);

    if (nSeqTotal)
        printf(">>> %sone sequence detected\n", (nSeqTotal > 1) ? "more than " : "");
}

然后将以下调试代码块插入到您看到/* Insert Debug Information Here */注释的函数中：

{
    int  nXIndex, nYIndex;
    int *pnValue;

    printf("Horizontal:\n");
    for (pnValue = panResult, nYIndex = 0; nYIndex < nHeight; nYIndex++, printf("\n"))
        for (nXIndex = 0; nXIndex < nWidth; nXIndex++, printf("%2i", *pnValue++));

    printf("\nVertical:\n");
    for (nYIndex = 0; nYIndex < nHeight; nYIndex++, printf("\n"))
        for (nXIndex = 0; nXIndex < nWidth; nXIndex++, printf("%2i", *pnValue++));
}

然后程序将产生以下输出：

Horizontal:
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 3 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 5 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 3 0 0 0 1 0 1 0 1 0 1 0 1 0

Vertical:
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 0 0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 0 0 0 0 2 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Grid has 6 contiguous sequences
>>> more than one sequence detected

但是，如果输入网格更改为此：

static char *s_szGrid =
    "X X X X X X X X X "
    " X X X X X X X X X"
    "X X X X X X X X X "
    " X X X X X X X X X"
    "X X X X X X X X X "
    " X X X X X X X X X"
    "X X X X X X X X X "
    " X X X X X X X X  "
    "X X X X X X X X XX";

然后输出将是：

Horizontal:
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 2 0

Vertical:
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

Grid has 1 contiguous sequences
>>> one sequence detected

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

2 回答 2

Related

Reference