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

Question

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

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

我用一个皇后随机填充每一行，在本例中用 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 个位于对角线上的方块排。要检查的列索引只是 c0+(r-r0) 和 c0-(r-r0).

Answer 2

通过反复试验，我能够使算法正常工作。这是遍历所有方向的循环：

function check(arr, row, col) {
    for (i = 0; i < arr.size(); i++) {} // left/right can be iterated as normal
    for (i = 0; i < arr.size(); i++) {} // top/down can be the same
    // lower-right diagonal from (row, col)
    for (i = row+1, j = col+1; i < arr.size() && i < arr.size(); i++, j++) {}
    // upper-left diagonal from (row, col)
    for (i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {}
    // lower-left diagonal from (row, col)
    for (i = row-1, j = col+1; i >= 0 && j < arr.size(); i--, j++) {}
    // upper-right diagonal from (row, col)
    for (i = row+1, j = col-1; i < arr.size() && j >= 0; i++, j--) {}
}

这当然只适用于方阵。

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

Check if an element of a 2D grid shares a diagonal, horizontal, or vertical with another element

c++

arrays

traversal

vector