c - 2D 配列内の非連続グループをチェックするためのより良いアルゴリズム

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 値の 2 つの連続していない「ブロック」があるかどうかをチェックするアルゴリズムが必要です。このアルゴリズムでは、特定の 2D ゲーム配列が与えられた場合、次のいずれかを決定できます。

はい、X の連続するブロックは 1 つだけです
いいえ、X の連続したブロックが複数あります

上記の例では、X の連続したブロックが複数あるため、「いいえ」が見つかります。

私の最初の簡単なアイデアは、X の 1 つの連続したブロックを見つけて、それらの値をカタログ化することです。この質問にとって重要ではない理由から、連続したブロックの途中で開始点を取得するのは簡単です。カタログ化されたリストにない場所で X を見つけることができれば、「いいえ」を返すことができます。それ以外の場合は「はい」を返すことができます。ただし、これはかなり非効率的な方法だと思います。

別の連続ブロックを包括的に除外するには、2D 配列のすべての項目に触れる必要があることを理解しています。「いいえ」を見つける最も簡単な方法にもっと興味があります。

配列はかなり小さいので、実際のパフォーマンスの問題なしにアイデアを実装できました。しかし、もっと洗練された方法があると確信しており、この問題は、スタックオーバーフローハイブマインドのアルゴリズムを愛する部分に興味があるかもしれないと考えました。

これは、別の SO の質問やインターネット全体のどこかに記述されている可能性もあります。質問の正しい言い方を知らないだけかもしれません。もしそうなら、私に教えてください。ベストソリューションは、まだ完成していない iOS ワードゲームの無料コピーも入手できます。:-D

score 2 · Accepted Answer

配列がグラフを形成し、グラフに複数の連結要素があるかどうかを尋ねています。これを行う最も簡単な方法は、おそらく配列をコピーし、見つけた最初の連結要素を消去してから、別の X を探すことです。1 つ見つかった場合、最初は複数の要素がありました。

消去は、グラフ検索の優れたアプリケーションです。たとえば、次のようにすることができます (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 )の実行時間としての次の最適解は、3 つ以上の連続したシーケンスがあるかどうかだけでなく、

見つかったシーケンスの正確な数を返します (水平および垂直)
は、すべてのシーケンスの位置と長さを、水平方向と垂直方向の両方で返します (コードをわずかに再配置します)。

問題の解決策は、グラフ理論を使用するのではなく、配列に関する知識を使用し、配列がメモリにどのように配置されているかについての知識を活用するだけで、非常に効率的かつ簡単に解決できます。次の 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 配列が最初から最後まで 1 回のパスで処理できる単純なフラットで連続したメモリブロックであることを理解することで、大幅な最適化が可能になることを意味します。

メモリ配置を利用して、である連続するメモリ位置ごとにインクリメントされる単一のカウンターのみを使用して水平シーケンスを追跡しX、非が検出されるたびにゼロにリセットできますX。配列の 2D ビューのすべての「行」の最後でカウンターが強制的にリセットされると、水平方向のシーケンスが正常に追跡されます。

水平方向のシーケンスが追跡されると同時に、垂直方向のシーケンスも同時に追跡できます。ただし、配列内の列内の隣接するセルはwidthバイト間隔で表示されるwidthため、列ごとに 1 つのシーケンスで行をスキャンするときに、行内で可能なすべての垂直シーケンスを追跡するカウンターの配列を保持する必要があります。

最後に、私のソリューションの本当の美しさは、カウンターが実際には 2 つの 2D 配列 (1 つは垂直シーケンスの追跡用、もう 1 つは水平シーケンスの追跡用) へのポインターであることです。各配列の各位置は、シーケンスの潜在的な開始を表し、関数が完了すると、各配列には、その位置から始まる各シーケンスの長さが各位置に含まれます。

これは、次の図を使用して最もよく示されています。

   Grid      Horizontal    Vertical
             Sequences    Sequences

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

Horizontal Sequences 配列の各桁は、その位置から始まる水平シーケンスの長さを表します。垂直シーケンスの垂直シーケンス配列についても同じことが言えます。

プログラムは入力配列を 1 つ、正確に 1 つ通過させ、各配列要素の処理時間は一定であるため、このアルゴリズムは 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 - 2D 配列内の非連続グループをチェックするためのより良いアルゴリズム

2 に答える 2

Related

Reference