Java中检查二维数组邻居的更高效方法

Question

大家好，我在几个大学作业中需要检查二维数组（网格）中的相邻单元格。我的解决方案使用异常有点像一个hack，我正在寻找一种方法来清理它，而不必像我的一些同学一样使用大量的 if 语句。我目前的解决方案是：

for ( int row = 0; row < grid.length; row++ ) {
    for ( int col = 0; col < grid.length; col++ ) {
        // this section will usually be in a function
        // checks neighbours of the current "cell"
        try {
            for ( int rowMod = -1; rowMod <= 1; rowMod++ ) {
                for ( int colMod = -1; colMod <= 1; colMod++ ) {
                    if ( someVar == grid[row+rowMod][col+colMod] ) {
                        // do something
                    }
                }
            }
        } catch ( ArrayIndexOutOfBoundsException e ) {
            // do nothing, continue
        }
        // end checking neighbours
    }
}

我不敢想象使用异常让我的代码能够工作的低效率，因此我正在寻找建议，以便在不影响可读性的情况下消除对异常的依赖，如果可能的话，并使这段代码更加高效。提前感谢。

- Sean Kelleher

---

不想过多指责，但异常应该是为了一些特殊情况而存在的。最好在事先验证输入，尤其是在琐碎的情况下。否则，您可能会掩盖重要的异常，并隐藏算法中的缺陷。 - user166390

我更希望摆脱这些例外，这也是为什么我不想只把它当成一个简单的解决方案。虽然我只是为了完成任务而匆忙处理，但我并不满足于此。 - Sean Kelleher

Answer 1

你可以尝试这个方法。 首先决定网格的大小，假设是8 x 8，并且指定MIN_X = 0，MIN_Y = 0，MAX_X = 7，MAX_Y = 7。 你当前的位置由thisPosX和thisPosY表示，然后尝试以下方法：

int startPosX = (thisPosX - 1 < MIN_X) ? thisPosX : thisPosX-1;
int startPosY = (thisPosY - 1 < MIN_Y) ? thisPosY : thisPosY-1;
int endPosX =   (thisPosX + 1 > MAX_X) ? thisPosX : thisPosX+1;
int endPosY =   (thisPosY + 1 > MAX_Y) ? thisPosY : thisPosY+1;


// See how many are alive
for (int rowNum=startPosX; rowNum<=endPosX; rowNum++) {
    for (int colNum=startPosY; colNum<=endPosY; colNum++) {
        // All the neighbors will be grid[rowNum][colNum]
    }
}

你可以在两个循环中完成它。

- Vivek

---

是的，我已经思考了一段时间这个问题，我认为我想到的最好的解决方案非常类似于这个，只不过我使用Math.max和Math.min来代替显式的比较/赋值。 - Sean Kelleher

Answer 2

所以，row和col目前包含我想要检查邻居的单元格的坐标。如果我有一个名为START_OF_GRID的类变量，其中包含0，我的解决方案如下：

int rowStart  = Math.max( row - 1, START_OF_GRID   );
int rowFinish = Math.min( row + 1, grid.length - 1 );
int colStart  = Math.max( col - 1, START_OF_GRID   );
int colFinish = Math.min( col + 1, grid.length - 1 );

for ( int curRow = rowStart; curRow <= rowFinish; curRow++ ) {
    for ( int curCol = colStart; curCol <= colFinish; curCol++ ) {
        // do something
    }
}

- Sean Kelleher

---

由于某些原因（可能是我做错了），Vivek的解决方案对我不起作用（它只检查4个单元格而不是8个）。你的方法很好用！谢谢。 - Vignesh

Answer 3

为什么不能在访问数组之前检查行+行模数和列+列模数的有效性?

可以像这样做:

 r=row+rowMod;
 c=col+colMod;
 if (r < 0 || c < 0 || r >= grid.length || c >= grid.length) continue;

另外一种选择（无需继续）：

 if (r >= 0 && c >= 0 && r < grid.length && c < grid.length && 
     someVar == grid[r][c]) { /* do something */ }

- DennyRolling

---

一个很好的解决方案，比我的效率更高，但我仍认为它有点hacky，因为我已经学会避免使用break和continue。非常感谢您的答案。 - Sean Kelleher

如果你害怕继续执行，只需反转条件并将其添加到if语句中。 - DennyRolling

我真的很喜欢它；它很小，不会越界。 - Nathan Goings

Answer 4

基本原则是不要访问超出范围的东西——所以要么保护边界，要么一开始就不要越界。也就是说，从一个你不会立刻越界的地方开始，并在越界之前停止。

for ( int row = 1; row < grid.length - 1; row++ ) {
    for ( int col = 1; col < grid.length - 1; col++ ) {
        // this section will usually be in a function
        // checks neighbours of the current "cell"
        for ( int rowMod = -1; rowMod <= 1; rowMod++ ) {
            for ( int colMod = -1; colMod <= 1; colMod++ ) {
                if ( someVar == grid[row+rowMod][col+colMod] ) {
                    // do something
                }
            }
        }
        // end checking neighbours
    }
}

与您目前的代码类似，该代码并不一定能够正确处理边缘情况 -- 也就是说，它在矩阵中适用一个3x3的网格，但在矩阵的边缘并不会将网格缩小为2x2、2x3或3x2。然而，在主体部分检查3x3网格的方法可以观察矩阵中的每个单元格。

- Mark Elliot

---

通常被称为“守卫”。通常，“守卫”单元格（例如第0列中的单元格）将包含某些特殊值，这些值将导致无操作或易于处理。 - user166390

是的，这可能是我的ConnectFour程序的解决方案，因为我只是检查相邻的连接，但在GameOfLife程序中它不会正确计算相邻的细胞。我不一定需要检查每个单元格，而是找到每个单元格的邻居数量（指定条件）。不过还是谢谢你的回答。 - Sean Kelleher

Answer 5

private void fun(char[][] mat, int i, int j){
    int[] ith = { 0, 1, 1, -1, 0, -1 ,-1, 1};
    int[] jth = { 1, 0, 1, 0, -1, -1 ,1,-1};
     // All neighbours of cell
     for (int k = 0; k < 8; k++) {
            if (isValid(i + ith[k], j + jth[k], mat.length)) {
                //do something here 
            }
        }
}

private boolean isValid(int i, int j, int l) {
        if (i < 0 || j < 0 || i >= l || j >= l)
            return false;
        return true;
}

- Vikas Tiwari

---

请在答案中添加一些描述。@Vikas Tiwari - Rohit Poudel

更新的代码。您可以通过使用mat [i + ith [k]] [j + jth [k]]在注释区域中访问所有邻居。 - Vikas Tiwari

Answer 6

这个怎么样：

private static void printNeighbours(int row, int col, int[][] Data, int rowLen, int colLen)
{
    for(int nextR=row-1; nextR<=row+1; nextR++)
    {
        if(nextR<0 || nextR>=rowLen)
            continue;  //row out of bound
        for(int nextC=col-1; nextC<=col+1; nextC++)
        {
            if(nextC<0 || nextC>=colLen)
                continue;  //col out of bound
            if(nextR==row && nextC==col)
                continue;    //current cell
            System.out.println(Data[nextR][nextC]);
        }
    }
}

- sumit

Answer 7

如果我正确理解了您的代码，并且正确猜测了您的担忧，那么您正在尝试避免在感兴趣的单元格位于网格边缘时检查不存在的邻居。一种方法（可能适用于您的应用程序）是在整个网格周围放置一个1单元宽的边框。然后，您在扩展网格的内部运行循环，并且您检查的所有单元格都有4个邻居（如果计算对角线相邻单元格，则为8个）。

- High Performance Mark

---

这个与Mark E的解决方案结合起来，将会是一个完美的解决方案，谢谢。 - Sean Kelleher