Каково значение инициализации массивов направлений с заданными значениями при разработке шахматной программы?
Я новичок в конкурентном программировании, и я часто замечал, что многие великие программисты имеют в коде следующие четыре строки (особенно в тех, которые используют массивы):
int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
Что это действительно означает и для чего используется техника?
Решение
Это метод кодирования всех направлений в виде массивов — каждая пара di[i],dj[i] это другое направление.
Если мы представим, что у нас есть кусок в местоположении x, y, и мы хотим добавить к его x и его значению y, чтобы переместить его в соседнее местоположение, 1,0 это восток, -1,0 это запад, 0,1 юг, 0, -1 север и так далее.
(Здесь я сказал, что верхний левый угол равен 0,0, а нижний правый — 4,4, и показано, как будет двигаться каждый указатель массивов из центральной точки, X, в 2,2.)
.....
.536.
.1X0.
.724.
.....
Как это настроено, если вы делаете ^1 (^ будучи битовым XOR) в индексе вы получаете противоположное направление — 0 и 1 противоположны, 2 и 3 противоположны и так далее. (Другой способ настроить это — по часовой стрелке, начиная с севера, затем ^4 получает вас в обратном направлении.)
Теперь вы можете проверить все направления из данной точки, пройдя по di а также dj массивы, вместо того, чтобы записывать каждое направление в отдельной строке (всего восемь!) (только не забудьте выполнить проверку границ :))
diK а также djK сформировать все рыцари направления вместо всех смежных направлений. Вот, ^1 будет переворачиваться вдоль одной оси, ^4 даст рывок противоположного рыцаря.
.7.6.
0...5
..K..
1...4
.2.3.
Другие решения
Для тех, кому затруднительно следовать объяснениям Паташу, я попытаюсь уточнить.
Представьте, что вы пытаетесь рассмотреть каждый возможный ход из данной точки на шахматной доске.
Если вы зациклите массивы di и dj, интерпретируя значения di как смещения x, а значения dj как смещения y, вы охватите каждое из 8 возможных направлений.
Предполагая, что положительный x — это восток, а положительный y — юг (как в ответе Паташу), вы получите следующее;
| ди / х | DJ / Y | направление - + ------ + ------ + ----------- 0 | 1 | 0 | восток 1 | -1 | 0 | запад 2 | 0 | 1 | юг 3 | 0 | -1 | к северу 4 | 1 | 1 | юго-восток 5 | -1 | -1 | северо-Запад 6 | 1 | -1 | к северо-востоку 7 | -1 | 1 | юго-запад
Массивы diK и djK можно интерпретировать одинаково, чтобы определить возможные ходы для фигуры рыцаря. Если вы не знакомы с шахматами, рыцарь движется по схеме L — два квадрата в одном направлении, а затем один квадрат под прямым углом к этому (или наоборот).
| диК / х | djK / y | направление - + ------- + ------- + ---------------- 0 | -2 | -1 | 2 запад, 1 север 1 | -2 | 1 | 2 на запад, 1 на юг 2 | -1 | 2 | 1 запад, 2 юг 3 | 1 | 2 | 1 восток, 2 юг 4 | 2 | 1 | 2 на восток, 1 на юг 5 | 2 | -1 | 2 на восток, 1 на север 6 | 1 | -2 | 1 восток, 2 севера 7 | -1 | -2 | 1 запад, 2 север
Небольшой фрагмент кода для проверки количества возможных перемещений во всех направлениях, который использует определенные массивы.
int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking
for (int d=0; d<8; d++) {
for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
movesPossible[d] = move-1;
}