c# - 翻牌游戏

Question

我需要帮助来构建一个算法来解决翻转游戏:给定一个整数“n”，形成一个由 1 和 0 组成的 n x n 方 block 。我必须将所有的 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) 时间复杂度(如果它很小，你可以天真地翻转矩形)。