解谜游戏 | 感受算法的魅力

柔光的暖阳◎ 2022-12-05 10:27 180阅读 0赞

> ## 3. 解谜游戏 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年09月7日 星期一 09:00</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年09月15日 星期二 09:00</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年10月10日 星期六 23:00</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **Description**
> 
> 小张是一个密室逃脱爱好者，在密室逃脱的游戏中，你需要解开一系列谜题最终拿到出门的密码。现在小张需要打开一个藏有线索的箱子，但箱子上有下图所示的密码锁。
> 
> ![20200910021402381.png][]
> 
> 每个点是一个按钮，每个按钮里面有一个小灯。如上图，红色代表灯亮，白色代表灯灭。每当按下按钮，**此按钮的灯**以及其**上下左右****四个方向按钮的灯**状态会改变（如果原来灯亮则灯灭，如果原来灯灭则灯亮）。如果小张通过按按钮将灯全部熄灭则能可以打开箱子。
> 
> 对于这个密码锁，我们可以先按下左上角的按钮，密码锁状态变为下图。
> 
> ![20200910021402373.png][]
> 
> 再按下右下角的按钮，密码锁状态变为下图。
> 
> ![20200910021402380.png][]
> 
> 最后按下中间的按钮，灯全部熄灭。
> 
> ![20200910021402238.png][]
> 
> 现在小张给你一些密码锁的状态，请你告诉他最少按几次按钮能够把灯全部熄灭。
> 
> **Input**
> 
> 第一行两个整数[![n,m(1 \\leq n,m \\leq 16 )][n_m_1 _leq n_m _leq 16]][n_m_1 _leq n_m _leq 16 _n_m_1 _leq n_m _leq 16]。
> 
> 接下来[![n][]][n 1]行，每行一个长度为[![m][]][m 1]的01字符串，0表示灯初始状态灭，1表示灯初始状态亮。
> 
> **Output**
> 
> 一行一个整数，表示最少按几次按钮可以把灯全部熄灭。
> 
> **Notes**
> 
> 第一个样例见题目描述，第二个样例按左上和右下两个按钮。
> 
> **测试用例保证一定有解**。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=202009&amp;test=129507&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>3&nbsp;3↵</li> 
>      <li>100↵</li> 
>      <li>010↵</li> 
>      <li>001↵</li> 
>     </ol></td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=202009&amp;test=129507&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>3↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>   <tr> 
>    <td>测试用例 2</td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=202009&amp;test=129508&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>2&nbsp;3↵</li> 
>      <li>111↵</li> 
>      <li>111↵</li> 
>     </ol></td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=202009&amp;test=129508&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>2↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

此题emmm，我想到了两种方法：高斯消元法 or 深度优先搜索。如果都是初次接触的话，那应该理解起来有难度，但是不能完全理解也没关系，多看几遍多敲几遍就好了...都是这么过来的...

下面讲讲深度优先搜索（dfs）的办法。

你可以这样理解深搜：依次**枚举**所有情况，直到枚举完，我们就搜索到一个结果。

--------------------

### 思路 ###

针对这个题，求最少按键次数，首先要知道：

*  一个按键最多按一次：如果有两次及以上，那么就会产生抵消，那么你的步骤肯定不是最少的。
 *  按键的顺序和最终结果无关：同样按下几个按键，以不同顺序去按下当然结果相同。

如果我们**暴力枚举**：对每一个按键有两种情况（按下 or 不动），那么我们最多需要枚举 ![2^\{16\\ast 16\}][2_16_ast 16]次，这真是个可怕的数字...那肯定有更优的算法。emmm下面的思路的来由只可意会不可言传，不说咋想出来的了，你看完这个方法能懂就够了。直接上**核心算法**吧：

1.   首先我们**仅枚举第一排灯的按键方式**：那么我们最多需要枚举 ![2^\{16\}][2_16]次，还算可以接受...记录下每次枚举的情况下第一排按下的次数count
2.  对于每一种枚举的结果（第一排灯已经操作完），我们接下来**依次逐行处理**。（比如说第一行某几个灯亮着，我们按下它们对应下一行的灯，这样第一行的灯我们通过第二行按键全部熄灭掉了；接着我们再讨论第二行，用第三行的按键将第二行全部熄灭...以此类推）。如果最后将倒数第二排搞定后，最后一排也全灭了，说明这个枚举是可行的，记录整个过程中的按键次数cur；否则，这个枚举不可行的，我们需要重新寻找其他枚举方案。
3.  对于某次枚举下，接着逐行操作成功全熄灭，那么说明我们用 count + cur 次数完成，这个时候要**更新答案的最小值。**

--------------------

### 代码实现 ###

此题代码实现较复杂，锻炼编程能力。如果编不出来的话，不必太灰心，只能慢慢熟练了。**题解也很难把编程能力一股脑地塞给你，这种能力都是靠你一点点码出来的**，对吧~ 但是提供可读性较好的代码给大家参考，**学习编程很重要的部分就是学习别人的代码**~

或许你还一股脑地将代码都写在可怜的 main 函数内（如果不是，就当我没说），提高程序可读性第一步：分功能写函数。

首先我先写几个要用到的**功能模块**（配合注释看应该可以看懂吧，不行的话先去学c/c++语法吧），后面都会被调用到的函数。全局变量有这些

#define MAX_LEN 17
    
    int n, m, a[MAX_LEN][MAX_LEN];  //题中的输入
    int cur[MAX_LEN][MAX_LEN];  //存储处理完第一排后的状态
    int ans = 256;   //存储答案：最小步骤。初始为最大值256步

**1、 实现对某一整数异或操作的函数**

/* 将p位置上的整数做一个反（异或）操作：
     * 1变成0， 0变成1 */
    void change(int *p) {
        if (*p == 1)
            *p = 0;
        else
            *p = 1;
    }

**2、 实现对灯按下的改变的函数**

/* 设定将a[i][j]处按下所产生的反应
     * 注意：a数组根据传递的地址而定 */
    void push(int a[][MAX_LEN], int i, int j) {
        change(&a[i][j]);
        if (i - 1 >= 0)
            change(&a[i - 1][j]);
        if (j - 1 >= 0)
            change(&a[i][j - 1]);
        if (i + 1 < n)
            change(&a[i + 1][j]);
        if (j + 1 < m)
            change(&a[i][j + 1]);
    }

**3、深度优先搜索（枚举第一排灯的按键情况）**

这里先不管第8行调用到的calc函数，你只要直到calc函数可以对某次枚举情况计算处后续的步骤数目即可。一层层理解，先理解dfs的操作，这是最难懂的。说句题外话，我第一次写dfs程序也很晕...dfs本质是递归嘛，看dfs程序的秘诀就是：**宏观地去看，当递归地调用自身时，你宏观理解此处递归调用的结果，不必过于深入递归函数纠结。**（emmmm如果这句话不能理解的话，你早晚会懂的...在经历了很多次复杂递归的毒打之后，你会很认可这句话的）

比如，我带着你理解下面这个dfs：

我们对第一排第step-1位按键的选择枚举：先按下，然后考虑下一位按键的枚举；还原（即不按下），然后考虑下一位按键的枚举。如果你能宏观地理解了这个思路，你再仔细去深究这个代码的递归实现，这样会理解得快很多。（如果你是大佬就当我没说，如果你没懂那你就再在多看几遍）。

/* 深度优先搜索,枚举第一排按键的所有按法
     * step: 当前讨论第1排第step + 1个按键
     * count: step之前按键一共被操作了的次数和 */
    void dfs(int step, int count) {
        // 深度优先搜索的终点：讨论完第一排最后一个按键了
        // 已经按照一种方式将第一排操作完成
        if (step == m) {
            int t = calc();  //计算该基础上熄灭所有的灯需要的步数
            if (t == -1)  //无解
                return;
            if (t + count < ans)  //有解，更新最小值
                ans = t + count;
            return;
        }
    
        push(a, 0, step);  //按下第一排第step-1个按键
        dfs(step + 1, count + 1);
    
        push(a, 0, step); //再次按下（相当于还原）第一排第step-1个按键
        dfs(step + 1, count);
    }

**4、calc函数**

在calc内调用了getCur()函数，主要是将枚举结果的状态拷贝到cur数组上，否则直接在a数组上操作很难还原，会对之后的讨论产生影响。calc函数的思路就是我们算法中总结的第二步，逐行熄灭。

/* 当第一排的灯被弄完后，把灯的状态复制到cur数组中
     * 便于后面的计数与操作，不会影响到原数组a */
    void getCur() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cur[i][j] = a[i][j];
    }
    
    /* 当第一排的灯被弄完后
     * 逐排操作，计算是否能够全部灭完
     * 如果不可以：返回-1；否则：返回操作次数 */
    int calc() {
        getCur();
        int step = 0;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < m; j++) {
                if (cur[i][j] == 1) {
                    step++;
                    push(cur, i + 1, j);
                }
            }
    
        for (int i = 0; i < m; i++)
            if (cur[n - 1][i] == 1)
                return -1;
        return step;
    }

--------------------

### 完整代码 ###

好了...小鸡翅简直太保姆了，还把一个个函数拆开讲...下面还是贴上完整代码吧，大佬们或许上来就可以来看完整代码。主要是小学期初期就写dfs，怕读者们接受不了，所以或许你会觉得我很啰嗦，可能深夜3点码下这篇题解的我确实比较啰嗦...

下面就是完整代码了，主函数里主要是在处理输入。特别要注意：**把每一行的换行符要吸掉！**不然...你不会知道小鸡翅为啥这个题一直到深夜才写出题解，因为一直因为每次没有吸去换行符而wa了一天...一直检查各种递归啊深搜啊的地方，结果2点debug出bug的我眼泪流下来...

#include <cstdio>
    
    #define MAX_LEN 17
    
    int n, m, a[MAX_LEN][MAX_LEN];
    int cur[MAX_LEN][MAX_LEN];  //存储处理完第一排后的状态
    int ans = 256;   //存储答案：最小步骤。初始为最大值256步
    
    /* 将p位置上的整数做一个反（异或）操作：
     * 1变成0， 0变成1 */
    void change(int *p) {
        if (*p == 1)
            *p = 0;
        else
            *p = 1;
    }
    
    /* 设定将a[i][j]处按下所产生的反应
     * 注意：a数组根据传递的地址而定 */
    void push(int a[][MAX_LEN], int i, int j) {
        change(&a[i][j]);
        if (i - 1 >= 0)
            change(&a[i - 1][j]);
        if (j - 1 >= 0)
            change(&a[i][j - 1]);
        if (i + 1 < n)
            change(&a[i + 1][j]);
        if (j + 1 < m)
            change(&a[i][j + 1]);
    }
    
    /* 当第一排的灯被弄完后，把灯的状态复制到cur数组中
     * 便于后面的计数与操作，不会影响到原数组a */
    void getCur() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cur[i][j] = a[i][j];
    }
    
    /* 当第一排的灯被弄完后
     * 逐排操作，计算是否能够全部灭完
     * 如果不可以：返回-1；否则：返回操作次数 */
    int calc() {
        getCur();
        int step = 0;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < m; j++) {
                if (cur[i][j] == 1) {
                    step++;
                    push(cur, i + 1, j);
                }
            }
    
        for (int i = 0; i < m; i++)
            if (cur[n - 1][i] == 1)
                return -1;
        return step;
    }
    
    /* 深度优先搜索,枚举第一排按键的所有按法
     * step: 当前讨论第1排第step + 1个按键
     * count: step之前按键一共被操作了的次数和 */
    void dfs(int step, int count) {
        // 深度优先搜索的终点：讨论完第一排最后一个按键了
        // 已经按照一种方式将第一排操作完成
        if (step == m) {
            int t = calc();  //计算该基础上熄灭所有的灯需要的步数
            if (t == -1)  //无解
                return;
            if (t + count < ans)  //有解，更新最小值
                ans = t + count;
            return;
        }
    
        push(a, 0, step);  //按下第一排第step-1个按键
        dfs(step + 1, count + 1);
    
        push(a, 0, step); //再次按下（相当于还原）第一排第step-1个按键
        dfs(step + 1, count);
    }
    
    int main() {
        scanf("%d%d\n", &n, &m);  //一定要加上\n，作用：吸去换行符
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c;
                c = getchar();
                a[i][j] = c - '0';  //将字符转化为整数考虑
            }
            getchar();  //吸去换行符
        }
    
        dfs(0, 0);
        printf("%d\n", ans);
    }

--------------------

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

[20200910021402381.png]: /images/20221123/0376b768537a43ecbd9380ed1bb22ee2.png
[20200910021402373.png]: /images/20221123/d13fd51e07ea4b38848ebe06ce0760db.png
[20200910021402380.png]: /images/20221123/a74dabe747c54843825064007031c2c4.png
[20200910021402238.png]: /images/20221123/9a864a8edec04b2c9cfb7f31bc561eca.png
[n_m_1 _leq n_m _leq 16]: https://img-service.csdnimg.cn/img_convert/f275112b02c3709f2d484fab1d10729d.png
[n_m_1 _leq n_m _leq 16 _n_m_1 _leq n_m _leq 16]: /images/20221123/e02e80b984784b92a495e9ba9b3a88df.png
[n]: https://img-service.csdnimg.cn/img_convert/fbceb7fe8529424e242261430f59993b.png
[n 1]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20n%20
[m]: /images/20221123/7c5fa325fb794a88826dc5060ef03525.png
[m 1]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20m%20
[2_16_ast 16]: https://private.codecogs.com/gif.latex?2%5E%7B16%5Cast%2016%7D
[2_16]: https://private.codecogs.com/gif.latex?2%5E%7B16%7D