pascal关灯问题程序

来源：百度知道 编辑：UC知道 时间：2024/05/11 16:34:03
题目:
关灯游戏：
在举行宴会的房间的一面墙上，30盏 彩灯排成5行6列，每盏灯带有1个开关。按动某盏灯的开关，它和它上下 左右的灯都会转变状态。
宴会之后，这些彩灯有开有关，愁煞 了管理员。如何才能将这些彩灯统统关上呢？

基础题。。
先发点牢骚。。这题根本不是，或者根本不能搜索，DP也没必要。。
话说这是一个经典的模型，楼主需要牢记此类算法及其优化。
我们很容易知道，由于每关一盏灯，这盏灯的上下左右的灯的状态都会改变，所以，假设有相邻两行r1和r2，r1在r2的上方，则r1的最终状态只和r2有关，也就是说，当我们确定了某行时，这行的上一行的状态就已经是固定的了！所以说，如果要关上所有的灯，我们不妨从第一行往下递推：枚举第一行的状态，那么这一行中亮着的灯对应的下一行的那盏灯的状态肯定要改变，而已经灭的则必然不需要修改！如此递推到最后一行，看看最后一行在进行完对上一行的操作后是否是全部关上的状态，如果是，则这次递推是成功的，即生成了一种关灯方案，若还有亮着的灯，则此次递推不成功，继续循环。
楼主貌似是要所有的关灯方案，那么，就只需要把第一行的所有状态都枚举一遍就可以了，这样的时间复杂度非常小，可以认为和O(10^2)同一个数量级的。如果要找操作次数最少的操作方案，只需要枚举第一行然后记录每次递推的次数即可。
当然，此题的衍生题目不少，还可能出现一定需要二进制优化的题目，还可能出现枚举第一列的情况，视具体情况而定了~~
如果还有问题，请直接PM我，我觉得你是没有思路吧。。思路以上已经给出了，程序自己写的话可以加深理解，我这里就先不给出了。。如果你执意要的话，PM我我可以给你。。
希望能够采纳我的答案~~

给个样例，不然不好分析

应该是穷举回溯,不排除DP的可能性
要题解找我,zyh617517224@163.com

可以尝试搜索吗?