1

Cの2進数のみの2D配列で任意の要素の8つの隣接要素をすべてチェックしたい場合、よりスマートな解決策があるかどうかを考えていました

私がすることは：

疑似コード:

//return how many neighbor of an element at x,y equals 1.
int neighbor(int** array, int x, int y)
    if x>WIDTH
        error
    if y>HIEGHT 
        error
    if x==0
        ignore west, nw, sw, and calculate the rest.....
    etc..

これはかなり退屈です。よりスマートなソリューションはありますか?

4

3 に答える 3

3

Adjacent Minesの特定のセルを取得するために、同様のアプローチを使用しましたMinesweeper Game。私がしたことは、次のような配列を使用したことです (MAX_NUMBER_OF_CELLS = 8) :

int offset[MAX_NUMBER_OF_CELLS][2] = {
                                            {-1, -1},
                                            {-1, 0},
                                            {-1, 1},
                                            {0, -1},
                                            {0, 1},
                                            {1, -1},
                                            {1, 0},
                                            {1, 1}
                                         };

マトリックスのCELLatについて話していることを考慮してください。隣接する CELL が有効な CELL であるかどうか (つまり、マトリックス内に収まるかどうか) をチェックするlocation 0, 0ために、これらのオフセット値を単純に追加します。CELLそれがVALIDである場合、それが含まれているかどうかを確認し1ます。sum1

//rest of the values represent x and y that we are calculating
(-1, -1)           (-1, 0)               (-1, 1)
           -------------------------
 (0, -1)   |(0, 0(This is i and j))|     (0, 1)
           -------------------------
 (1, -1)           (1, 0)                (1, 1)

sum = 0;
for (k = 0; k < MAX_NUMBER_OF_CELLS; k++)
{
    indexX = i + offset[k][0];
    indexY = j + offset[k][1];
    if (isValidCell(indexX, indexY, model)) // Here check if new CELL is VALID
                                            // whether indexX >= 0 && indexX < rows
                                            // and indexY >= 0 && indexY < columns
    {
        flag = 1;
        if (arr[indexX][indexY] == 1))
            sum += 1;
    }
}

編集1：

ここに1つの実用的な例があります（Cは私の言語ではありませんが、それでもあなたに1つのアイデアを与えるためにそれを試してみました:-)）：

#include <stdio.h>
#include <stdlib.h>

int findAdjacent(int [4][4], int, int, int, int);

int main(void) 
{
    int arr[4][4] = {
        {0, 1, 0, 0},
        {1, 0, 1, 1},
        {0, 1, 0, 0},
        {0, 0, 0, 0}
    };
    int i = 2, j = 2;
    int sum = findAdjacent(arr, i, j, 4, 4);
    printf("Adjacent cells from (%d, %d) with value 1 : %d\n", i, j, sum);
    return EXIT_SUCCESS;
}

int findAdjacent(int arr[4][4], int i, int j, int rows, int columns)
{
    int sum = 0, k = 0;
    int x = -1, y = -1; // Location of the new CELL, which
                        // we will find after adding offsets
                        // to the present value of i and j
    int offset[8][2] = {
        {-1, -1},
        {-1, 0},
        {-1, 1},
        {0, -1},
        {0, 1},
        {1, -1},
        {1, 0},
        {1, 1}
    };
    for (k = 0; k < 8; k++)
    {
        x = i + offset[k][0];
        y = j + offset[k][1];
        if (isValidCell(x, y, rows, columns))
        {
            if (arr[x][y] == 1)
                sum += 1;
        }
    }

    return sum;
}

int isValidCell(int x, int y, int rows, int columns)
{
    if ((x >= 0 && x < rows) && (y >= 0 && y < columns))
        return 1;
    return 0;
}
于 2013-10-06T08:04:41.010 に答える
1

考えられる最適化の 1 つは、セルを変更するよりも多くのセルの近傍数を知りたい場合、各セルの近傍数を前処理し、結果を別の配列に保存することです。

int** actualArray;
// fill in with 0s and 1s
int** numberOfNeighbors;
// write a function to calculate the number of neighbors for cell x,y in actualArray and
// store the result in numberOfNeighbors[x][y]
preprocess(actualArray, numberOfNeighbors); // call this whenever actualArray changes
// now you can get the number of neighbors of a cell in constant time
// from numberOfNeighbors[x][y]
于 2013-10-06T07:40:25.503 に答える