c++ - 检查二维网格的元素是否与另一个元素共享对角线、水平线或垂直线

Question

我正在研究 n 皇后问题，其中一部分是检查皇后是否受到另一个皇后的威胁以确定良好的棋盘状态。

我有一个用 0 填充的二维数组，在这个例子中是一个 4x4:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

我用一个皇后随机填充每一行，在本例中用 1 表示:

0 0 1 0
1 0 0 0 
1 0 0 0
0 0 0 1

我需要检查有多少其他棋子威胁到给定棋子。如果一个蚁后与另一个蚁后共享一条水平线、对角线或垂直线，就会受到威胁。

但是，我不完全确定如何沿对角线遍历数组。

int checkThreats(vector<vector<int> > board, int r, int c) {
    int threats = 0;
    // checks vertical and horizontal
    for (int i = 0; i < board.size(); i++) {
        if (board[i][c] == 1 || board[r][i] == 1) {
            threats++;
        }
    }
    // it will count itself as a threat, so less one
    threats--;
    return threats;
}

这是水平和垂直检查的算法。给定棋盘上的位置 r, c，它会检查左、右、上和下位置(十字 + 形状)中存在多少个皇后。

取1, 0的坐标r, c，检查的位置用x标记，用 >o 如果存在威胁:

x 0 1 0
o x x x
o 0 0 0
x 0 0 1

在这种情况下，threats == 1 因为我们不计算原始位置。

我的问题是试图沿着对角线找到 X 形的碎片。

Answer 1

对角线的诀窍在于它们的长度各不相同(总长度和单独长度；考虑到它们仅包含从棋盘的边缘或角开始的 3 个正方形，但从中间开始有 5 个正方形)。这种不规则性使它们更难解释。

一种策略是遍历(比方说)行，为每一行考虑 0(如果它是受试者的行)、1(如果一个不在棋盘上)或 2 个位于该行对角线上的方 block 。要检查的列索引只是 c0+(r-r0) 和 c0-(r-r0)。