"direction X-Y delta pairs for adjacent cells"的含义

Question

我正在尝试理解名为"Boggle"的游戏算法在N*N矩阵中查找单词。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 6; // max length of a word in the board
char in[N * N + 1]; // max length of a word
char board[N+1][N+2]; // keep room for a newline and null char at the end
char prev[N * N + 1];
bool dp[N * N + 1][N][N];
 // direction X-Y delta pairs for adjacent cells
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
bool visited[N][N];
bool checkBoard(char* word, int curIndex, int r, int c, int wordLen)
{
if (curIndex == wordLen - 1)
{
    //cout << "Returned TRUE!!" << endl;
    return true;
}
int ret = false;
for (int i = 0; i < 8; ++i)
{
    int newR = r + dx[i];
    int newC = c + dy[i];
    if (newR >= 0 && newR < N && newC >= 0 && newC < N && !visited[newR]        [newC] && word[curIndex+1] == board[newR][newC])

我不明白这部分:

 // direction X-Y delta pairs for adjacent cells
 int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
 int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

为什么这些数组有它们所拥有的值，为什么这样做?

Answer 1

这些数组表示当前"光标"位置(在代码中作为变量c, r跟踪的x,y坐标)的行和列偏移量的可能组合:

 // direction X-Y delta pairs for adjacent cells
 int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
 int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

例如，如果您想象一个3x3的正方形网格，并认为中心框是当前位置，那么其他8个周围的单元格是由这些行和列偏移集指示的。如果我们在索引2处取偏移量(dx[2] = 1和dy[2] = 0)，这将表示下一行的单元格(并且向左/向右移动零)。