1

我一直在考虑是否有任何更聪明的解决方案，如果我想检查二进制数中任意元素的所有八个邻居，只有 C 中的二维数组

我要做的是：

伪代码：

//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 location 0, 0。我们将简单地添加这些偏移值，CELL以检查相邻的 CELL 是否是有效的 CELL（即它落在矩阵内）。如果它是VALID，那么我们将查看它是否包含1，如果是而不是sum通过1否则不增加。

//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：

这是一个工作示例（C 不是我的语言，尽管我仍然尝试使用它来给你一个想法:-)）：

#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

您是否试图找到数组中元素的当前位置？如果是这样，您可以定义一个宏，如：

#define OFFSET(x,y) ((GridWidth*y)+x)

或者，如果您试图找出哪些周围的“盒子”可能包含一个元素（即哪些邻居是“在界限内”）......

for k = 0 while k < GridWidth
    for m = 0 while m < GridWidth
        if k < GridWidth
            toRight = true
        if m < GridWidth
            toDown = true
        if k > 1
            toLeft = true
        if m > 1
            toUp = true

从那里，结合方向得到对角线 -if toRight && toUp, then toUpRight=true等等

编辑 - 我忘了提，这是如果网格存储在一维数组中。对于 2d，m 将用于 GridHeight

于 2013-10-06T08:06:12.497 回答
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 回答