以模环绕网格

Question

我正在尝试编写一个程序，在20x60个单元格的网格上实现Conway's Game of Life。网格应该环绕，使左侧连接到右侧，顶部连接到底部。

因此，任何位置为(0, col)的细胞在(maxRow, col)处都有一个邻居。任何位置为(row, 0)的细胞都有一个相邻的(row, maxCol)。

下面的函数应该计算相邻单元的数量。它适用于不在边上的坐标，但不适用于在边上的坐标。例如，如果有(0, 10), (0, 11), (0, 12)和(0, 10)点被传递给函数，它将返回一个大的数字作为邻居计数，而不是1。我知道mod操作符%会有帮助，但我不知道如何使用它。

{
    int i, j;
    int count = 0;
    for (i = row - 1; i <= row + 1; i++)
       for (j = col - 1; j <= col + 1; j++) 
           count += grid[i][j]; }
    if (row==maxrow-1 || row==0)
         count = count+ grid [(row-(maxrow-1))*-1][col-1]+grid[(row-(maxrow-1))*-1][col]+grid[(row-(maxrow-1))*-1][col+1];
    if (col==0 || col==maxcol-1)
         count=count +grid[row-1][(col-(maxcol-1))*-1]+grid[row][(col-(maxcol-1))*-1]+grid[row+1][(col-(maxcol-1))*-1];

    count -= grid[row][col];
    return count;
    } 

Answer 1

在提出解决方案之前，让我先做一些观察。

• 将一些网格值相加，然后减去其他网格值并不是一个好主意。您应该首先计算正确的网格坐标。

• 当你写count += grid[i][j];时，你正在使用可能无效的数组索引。例如，当row为零时，i = row - 1的i值为-1。

• 您的代码暗示maxrow是行数，因为您正在编写maxrow-1，但名称maxrow暗示最大行索引。这很令人困惑。最好将行数命名为numRows，然后最大的行索引是numRows - 1。同样，最好将maxcol替换为numCols。

现在进入问题的核心。row - 1可以等于-1, row + 1可以等于numRows。这两个都是无效的行下标。类似地，col - 1和col + 1会导致无效的列索引-1和numCols。解决这个问题的一种方法是测试这些特定的值，并用环绕索引替换它们:

int count = 0;
for (int i = row - 1; i <= row + 1; i++) {
  int R = i;
  if (R == -1) {
    R = numRows - 1;
  } else if (R == numRows) {
    R = 0;
  }
  for (int j = col - 1; j <= col + 1; j++) {
    if (i == row && j == col) {
      continue;  // Skip grid[row][col].
    }
    int C = j;
    if (C == -1) {
      C = numCols - 1;
    } else if (C == numCols) {
      C = 0;
    }
    count += grid[R][C];
  }
}

这是一种高性能的解决问题的方法，因为测试和赋值比取模更快，但它也需要大量的代码。在模运算符的帮助下，我们可以编写更简洁的代码。

我们想写i % numRows，但当i为-1时，c++将其计算为-1。这是因为模运算对于负值是不明确的，c++选择了一种不能保证非负结果的解释。

为了解决这个问题，我们在对numRows取模之前将numRows添加到i。这保证了我们总是取正数的模。现在我们可以计算grid[row][col]的8个邻居中活细胞的数量，如下所示。

int count = 0;
for (int i = row - 1; i <= row + 1; i++) {
  for (int j = col - 1; j <= col + 1; j++) {
    if (i == row && j == col) { 
      continue;  // Skip grid[row][col].
    }
    count += grid[(i + numRows) % numRows][(j + numCols) % numCols];
  }
}