107

我是竞争性编程的新手，我经常注意到，许多伟大的程序员在他们的代码中都有这四行（特别是在那些涉及数组的代码中）：

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 };

这真正意味着什么？技术的用途是什么？

4

3 回答 3

85

这是一种将所有方向编码为数组的技术——每一对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（^按位异或），你会得到相反的方向 - 0 和 1 是相反的，2 和 3 是相反的，依此类推。（设置它的另一种方法是从北开始顺时针方向 - 然后^4让你转向相反的方向。）

现在您可以通过遍历您的di和dj数组来测试给定点的所有方向，而不是需要在自己的行上写出每个方向（总共八个！）（只是不要忘记进行边界检查:)）

diK并djK形成所有骑士方向而不是所有相邻方向。在这里，^1会沿着一个轴翻转，^4会给对面的骑士飞跃。

.7.6.
0...5
..K..
1...4
.2.3.
于 2013-05-03T00:46:44.503 回答
65

对于那些发现 Patashu 的解释难以理解的人，我将尝试澄清。

想象一下，您正在尝试考虑从棋盘上给定点开始的每一个可能的移动。

如果您循环遍历 di 和 dj 数组，将 di 值解释为 x 偏移量，将 dj 值解释为 y 偏移量，则您涵盖了可能的 8 个方向中的每一个。

假设正 x 是东，正 y 是南（如 Patashu 的回答），你会得到以下结果；

  | 迪/x | DJ/年 | 方向
--+--------+------+----------
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 数组，以确定 Knight 棋子的可能移动。如果您不熟悉国际象棋，骑士会以 L 型移动 - 两个方格朝一个方向，然后一个方格与该方向成直角（反之亦然）。

  | 迪克/x | djK/年 | 方向
--+-------+--------+----------------
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北
于 2013-05-03T04:44:52.910 回答
1

一小段代码，用于检查所有方向上可能的移动量，它使用定义的数组。

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;
}
于 2013-05-29T12:20:57.640 回答