c# - 翻转瓷砖游戏

Question

我需要帮助构建一个算法来解决翻转游戏:给定一个整数“n”，形成一个由 1 和 0 组成的 n x n 正方形。我必须将所有 1 翻转为 0。虽然，您只能以矩形的形式翻转图 block (矩形中的所有内容都会被切换)，其中矩形的左上角顶点是正方形的左上角。我必须计算可以使全零切换的最小数量。

Answer 1

1. 如果解决方案是最优的，则没有矩形会被翻转超过一次(事实上，我们永远不能翻转它而不是翻转它两次)。

2. 翻转的顺序并不重要。

3. 因此，我们可以使用以下算法:

   for i = n - 1 downto 0
        for j = n - 1 downto 0
            if f[i][j] == 1
                flip(i, j) // This function should flip the entire rectangle
                res += 1
   

如果我们按照这个顺序处理单元格，后面的单元格永远不会影响任何前面的单元格。因此，我们要么翻转当前单元格，要么不翻转。

如果N很大，您可以使用矩形上的前缀和来确定我们是否需要进行翻转以获得O(N^2)时间复杂性(如果它很小，你可以天真地翻转矩形)。