Значение «пары дельта X-Y направления для соседних ячеек»;
Я пытаюсь понять алгоритм игры под названием «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};
Почему эти массивы имеют значения, которые они имеют, и почему это работает?
Решение
Эти массивы представляют возможные комбинации смещений строк и столбцов из текущего местоположения «курсора» (которое является координатой x, y, отслеживаемой в коде как переменные c,r):
// 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};
Например, если вы представляете квадратную сетку 3х3 и считаете центральное поле текущим местоположением, то остальные 8 окружающих ячеек — это те, которые обозначены этими наборами смещений строк и столбцов. Если мы взяли смещения по индексу 2 (dx[2] = 1 а также dy[2] = 0), это будет указывать на ячейку на одну строку вниз (и смещение нуля влево / вправо).
Другие решения