请教一道算法题

不知道小帅 发表于 2021-3-2 23:31
暴力是暴力，但是可以稍微聪明一点的暴力。这个题目的话，bfs/dfs都可以做。bfs的话就是说直接从目标状态开 ...

我也是这个思路。我记得这大致上就是A* algorithm吧？感觉解puzzle常用到。

楼主，贴题目一定要给范围。leetcode上很多题目根本就不给范围，这完全就是耍流氓。
题目条件范围不同很多时候就是不同的题目。
这个题思路是这样的：
任何一个点上的操作，要么做一次，要么不做。
有了这个性质之后，我们来看第一列或者第一行:
[ABCDEFG]
HIJKLMN
如果我们已经枚举[ABCDEFG]里每一个的操作情况，想要让ABCDEFG位置都变成1，
那么第二行HIJKLMN的操作情况已经确定了。
这样我们只需要枚举这第一行的操作，然后就可以顺推下来之后每行每个位置的操作情况。
这样的复杂度是O(2^M*N) M是小的那一条边(对列这个性质也成立，所以我们选择小的那一条边枚举)

另一个方法是把每个cell的操作看成一个变量X_{i,j}, 然后关于每个位置都能由它上下左右自身列出一个在(mod2)域里的方程。
求这个方程的一个可行解可以用高斯消元在多项式时间里解决。

GreatFootGeass 发表于 2021-3-10 23:50
很有意思的一个puzzle.
Lights out puzzle曾经是个电子游戏。这有个试玩版的：https://www.geogebra.org/m ...

解这种离散算法题目基本上都不需要这些convex optimization的方法，解方程或者状态压缩枚举就可以了。