问题是这样的。
有一个NXN棋盘。棋盘上的每一个方块可以是空的，也可以有一个车。我们所知道的车可以水平或垂直攻击。给定一个2D矩阵，其中0表示一个空正方形，1表示一个rook，我们必须用1填充矩阵中的所有单元格，1表示可以被棋盘上任何rook攻击的正方形。
现在，我可以在O（n ^ 3）时间和恒定的空间复杂度很容易地做到这一点。然后在O（n ^ 2）时间和O（2×n）空间复杂度。但我需要在O（n^2）时间和常数空间中求出一个解有人请帮忙。
最佳答案
假设你知道你的车不是在第一列就是在第一行。然后，只要遍历第一行/列并在每次看到rook时填充矩阵（除了在最后一步中填充第一行/第一列之外），就可以得到一个没有空间开销的o（n^2）解决方案。
如果所有rook都在最后一列/最后一行、第一列/最后一行和最后一列/第一行中，则相同。
现在获取初始矩阵并对其进行迭代，直到它包含一个rook我是这辆车那一行的索引，j是这辆车那一列的索引继续迭代矩阵，对于在位置（i'，j'）处找到的每个rook，将其移除，替换为位置（i，j'）处的rook和位置（i'，j'）处的另一个rook。
你最终得到的矩阵只有第i行和第j列。设A_1是由其i第一行和
j第一列。那么a_1的属性是它只在它的
最后一行/las列，因此您可以解决没有空间开销的问题对a的其他三个子矩阵（n-i+1最后一行和j第一列的子矩阵，依此类推）执行相同的操作。
如果不清楚，请告诉我，我会提供更多的细节。