题解 P1985 【[USACO07OPEN]翻转棋】

world_execute · 2019-02-05 16:36:23 · 题解

[ 更好的阅读体验 ]

[ 原题面 ]

第零部分 —— 阅读题目

• 题目大意：有 M*N 个格子，一面是白色，另一面是黑色。给你一个操作，翻转某个位置，使这个位置和与它有公共边的所有格子变换一次颜色（黑->白，白->黑）。现在，给你一个初始状态，问你如何翻转，才能使翻转次数最小，如有多个解，输出字典序最小的那个，如果无解，输出“IMPOSSIBLE"（忽略引号）

• 数据范围：1 ≤ M, N ≤ 15

• So，看到这个数据范围，是不是觉得出题人很良心，但在看完题目之后，发现 2^30 太大了 （连int都快存不下了） 几乎无法得分

第一部分 —— 开始分析

• 首先，我们可以从数据范围知道，单纯地去枚举每个位置的翻转情况是一定过不了全部的测试点的

• 这样枚举的时间复杂度约是 O（2^(n+m)），因为总共 n*m 个点，每个点可以反转或者不反转

• So，上面的时间复杂度是我们无法接受的，必须降下来

第二部分 —— 初现思路

• 通过题目我们可以知道，我们要把所有点反转成白色

• So，我们要尽可能地让某一部分都变成白色，然后在保证之前的白色部分不会缩小的条件下，慢慢地扩大，直到覆盖整个棋盘 （ 有没有一点像转魔方？ ）

第三部分 —— 深入思考

• 通过上面的分析，我想出一种方法 （当然，没看过题解 QAQ）：还是枚举 （善变的我）

• 先枚举第一行（其实枚举任何一行，或任何一列都可以得出结果，见延伸阅读① ）

• 再根据之前说的：“我们要慢慢扩大，直到覆盖整个棋盘” ，但是这句话的根本条件是保证白色部分不会缩小。

• So，如何保证白色区域不会缩小，是这道题的突破口

第四部分 —— 解决问题

• （这一部分的标题是不是很像大部分数学试卷的最后一大题？）

• 接着，分析题目，每一次反转，都会把一个“十”字形区域取反，it looks like this：

   ...+---+---+---+...
   ...|   | * |   |...
   ...+---+---+---+...
   ...| * | * | * |...
   ...+---+---+---+...
   ...|   | * |   |...
   ...+---+---+---+...
    （星号标注区取反）
     Tips: 取反  1->0  0->1 ,相当于 not 或 ! 
           但是代码中，本人喜欢使用 1-X 来取反

• （新奇的画风）

• 如果哪一格不是0的话，我们就可以在它的下方进行反转。（具体为什么是下方，见 延伸阅读① ）

• 使用这样的方法，除了第一行以外，我们都可以解决，只用在完成之后，判断一下，最后一行是不是都是0，如果是，我们就得出了一个答案，在加上一些判断，这部分代码就完成了

• 在这一部分代码完成是，我们还需要注意的是，每次都要出现一个Shadow数组，在每次操作 （骚操作？） 之前，必须保存现场，（Sounds like a search algorithm），在最后还原。

• So，在枚举时，我们用搜索解决好了 （这更体现出了我的善变， o(////▽////)q ） ，在加上前面的思路，与输入输出，代码就可以开始打啦。<(￣︶￣)↗[GO!]

第五部分 —— 代码实现

• 输入部分，我相信大家都写得出啦

• 反转部分，这十分的简单，但是要注意如果使用坐标位置不要搞混

• 搜索部分，万一有比我还弱的蒟蒻的话，我只好写出来了：

void Work(int k)
{
    if (!k) Doit();              // 全部枚举好了
    else
    {
        Work(k - 1);               // 递归不反转
        Reversal(1, k), ++b;       // 翻转一下，用来递归翻转情况
        Work(k - 1);               // 递归翻转
        Reversal(1, k), --b;       // 翻转一下，用来还原
    }
}

• 这个函数写的不是特别美观 （如果有 int main(){} 这样的函数就好了） 但也可以凑合看看

• 其中的 k 表示还有多少个位置没有选，b表示翻转了多少次，因为需要输出最少翻转次数

• 也许有的同学会问：为什么不用“选了多少个位置”来表示k呢？为了代码短，如果你有自己的习惯，请不要学本人

• Doit，这只需要把思路翻译成代码就好了，但是我还是觉得出示一下 伪 代码更好一点：

void Doit()
{
    Map = Shadow
    For (i = 1..n-1)
        For (j = 1..m)
            If (Map[i][j])
                Reversal(i+1,j),++p;//注意i从1到n-1
    Flag = 1;
    for (int j=1..m; Flag&=(!Map[n][j++]));     //判断最后一行是不是全为0
    if ((p+b<D || (p+b==D && Judger()) || D==-1) && Flag)
    {
        Ans = ans
        D = p+b
    }                                           //判断是否符合替换要求
    Shadow = Map
    Ans[2][1] ~ Ans[n][m] = 0
}

• 其中D表示目前最优解的反转次数，Judger表示与当前解进行字典序比较，其他就自己去理解吧。 (>▽<)

• 输出，相信你们会写的比本人好的，我就不浪费笔墨了，主要就是无解时需要输出“IMPOSSIBLE”需要注意

• So，第五部分的代码实现就解决了，是不是觉得还比较简单，还有本人第一次在洛谷发布题解，不知道如何写才好，如果有没讲清楚的地方，尽管在评论中回复，我尽量做到有问必答。

第六部分 —— 后记？

• 管理员大大要体谅我这个大年初一在家一个人码代码的人 （空巢寂寞老人？？？） 我已经尽力把这篇题解写好了，如果还有什么地方写的不好的 (因为我们是为人民服务的QAQ) ，我会继续改进的

• 当然，这不是真正的后记，还有延伸阅读没有写呢

• So，大家所期望的延伸阅读就成了第七部分 （也许只有我期望）

第七部分 —— 延伸阅读①

• 当然，并没有延伸阅读②

• 你可以选择任何一行或一列

• 如果你选择某一行，但是它不是第一行，或最后一行的话，那么每个数字，不管你想把他从“1”变成“0”，还是从“0”变成“0”，都会出现两种方案

• 因为在你想把“1”变成“0”时，可以在上方翻转，或是在下方翻转。当你想把“0”变成“0”时，有可能时上下都不翻转，或是上下同时翻转

• 这样，时间复杂度将会飙升，因为你又需要枚举的次数要增加 2^n 次，但最后总是能得出正确答案，但时间复杂度为 O(2^(n+1)+n^2)

• 列也一样，最好选择第一列或最后一列

• 这样，如果不是用第一行（列）或最后一行（列）的话，会非常麻烦，代码不好实现，时间复杂度也更打大，这是得不偿失的

• So，这就是为什么我用第一行作为起始行了 （当然，第一列也可以）

第八部分 —— 真·后记

• 不知不觉就写了这么多了呢，希望各位给我一个赞，或是给予我您的宝贵的意见

• So，题解就到这了吧