本帖最后由 aimisiyou 于 2020-9-12 07:48 编辑
.·.·. 发表于 2020-9-11 00:45
考虑1x2只有一盏灯亮的情形，你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自 ...
简单看成递归，即把第一行全部转为熄灭状态（即在原第一行亮灯的下方按钮按一下，可保证第一行灯全熄灭），这样递归下去就剩最后两行有亮有熄情况。
可得
mod(n1+n2+n4，2)=1
mod(n1+n2+n3+n5，2)=0
mod(n2+n3+n6，2)=0
mod(n1+n4+n5+n7，2)=0
mod(n2+n4+n5+n6+n8，2)=0
mod(n3+n5+n6+n9，2)=0
mod(n4+n7+n8，2)=0
mod(n5+n7+n8+n9，2)=0
mod(n6+n8+n9，2)=0
其中，ni={0,1}
本帖最后由 aimisiyou 于 2020-9-12 18:33 编辑
这取模的方程怎么求？人工分析好繁琐啊，能否编程求解？
4*4初始全亮，结果如图，最少是4步。看来右边的解（10步）不是最少步数。
n*m情况下复杂度为O（2^min{n,m}）
.·.·. 发表于 2020-9-11 00:45
考虑1x2只有一盏灯亮的情形，你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自 ...
如何求解方程组？
aimisiyou 发表于 2020-9-12 21:44
如何求解方程组？
先确定第一行灯的亮与灭
然后剩下的灯亮与灯灭可以直接推出
解方程组的话就是解一个mod2 意义下的方程组
跟上面的算法差不多
本帖最后由 aimisiyou 于 2020-9-13 07:17 编辑
.·.·. 发表于 2020-9-12 22:28
先确定第一行灯的亮与灭
然后剩下的灯亮与灯灭可以直接推出
1、与其说是解方程组，还不如说是给定初始值，得出推理结果，然后复核推理结果是否正确。
2、我考虑的是以min{n,m}为顶边，这样可减少运算量。
如将矩阵
1011010
0110101
0010111
1010011
旋转90度，得到矩阵
1001
0010
1111
0001
0110
1101
1110
aimisiyou 发表于 2020-9-12 22:41
1、与其说是解方程组，还不如说是给定初始值，得出推理结果，然后复核推理结果是否正确。
2、我考虑的是 ...
类似问题，如果只是求解，那么解方程组是最优算法（能确保在多项式时间判断题目是否有解）
但如果要求记录边数，只能给定初始值，得出推理结果
本帖最后由 aimisiyou 于 2020-9-12 23:26 编辑
.·.·. 发表于 2020-9-12 23:11
类似问题，如果只是求解，那么解方程组是最优算法（能确保在多项式时间判断题目是否有解）
但如果要求记 ...
解不唯一就很麻烦了。为了省去麻烦的奇偶判定，我直接枚举顶边按下次数的所有状态（2^min{n,m}）,得出最后一行的推理结果，然后复核最后一行的推理结果是否正确。若推理结果正确，则顶边的状态即为其中一个解。