在棋盘上寻找可被车攻击的方块

Question

问题是这样的..

有一个NxN的棋盘。棋盘上的每个方格可以是空的，也可以有车。我们所知道的车可以水平或垂直攻击。给定一个 2D 矩阵，其中 0 代表一个空方格，1 代表一个车，我们必须用 1 填充矩阵中的所有单元格，1 代表可以被棋盘上存在的任何车攻击的方格。

现在，我可以在 O(n^3) 时间和常量 space 复杂度内轻松完成此操作。然后在 O(n^2) 时间和 O(2*n) space 复杂度。但我需要在 O(n^2) 时间和常数 space 中找出一个解决方案。有人请帮忙。

Answer 1

试试这个解决方案

int main(){
    int n;
    int chess[64][64];
    int hor[64],ver[64];
    //read chessboard
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(chess[i][j] == 1){
                hor[i] = 1;
                ver[j] = 1;
            }
    int cntHor=0;
    int cntVer=0;
    for(int i=0; i<n; i++){
        if(hor[i] == 1) cntHor++;
        if(ver[i] == 1) cntVer++;
    }
    int result = (cntHor+cntVer)*n-cntHor*cntVer;
    cout<<result;
    return 0
}

Answer 2

假设您知道所有的车都在第一列或第一行。然后你会得到一个没有 space 开销的 O(n^2) 解决方案，只需遍历第一个 row/column 并在每次看到车时填充你的矩阵（除了填充第一行/第一列，你在最后一步处理）。如果所有的车都在最后一列/最后一行，第一列/最后一行，最后一列/第一行，这同样适用。

现在获取初始矩阵并对其进行迭代，直到它包含一个车。设 i 是该车所在行的索引，j 是其列的索引。继续遍历矩阵，对于您在位置 (i',j') 找到的每个车，将其移除并用位置 (i,j') 的车和位置 (i',j) 的另一个车替换它。

您最终得到的矩阵将只在第 i 行和第 j 列有一个。设 A_1 为 A 的第 i 行组成的子矩阵，并且 j 第一列。然后 A_1 有属性它只包含一个最后一行/las 列，因此您可以在没有 space 开销的情况下求解 A_1。对 A 的其他三个子矩阵（具有 n-i+1 最后一行和 j 第一列的子矩阵，依此类推）执行相同的操作。

如果不清楚请告诉我，我会提供更多细节。

在棋盘上寻找可被车攻击的方块

Finding Squares on the chessboard attackable by a rook

algorithm

chess

data-structures