algorithm - 一道关于开关控制的算法题

Question

你能帮我解决下面的问题吗...

有一个N*M表，每个cell都有一个开关，开关有两种状态---ON/OFF。 当我们改变一个开关的状态时，不仅它本身而且上下左右都改变了。 问题是编写一个程序找出并打印出关闭所有开关的最少步骤。如果不是，则打印 -1。

例如，下面是一个3*4的表格。 (※●为OFF，O为ON。)

图 1

●   ●   ●   ●
●   O   ●   ●
●   ●   ●   ●

现在我们将 (1,1) 单元格从 ON 更改为 OFF，然后表格将更改为下图。

图 2

●   O   ●   ●
O   ●   O   ●
●   O   ●   ●

当我们将 (0,2) 单元格从 OFF 更改为 ON 时，它将变为:

图 3

●   ●   O   O
O   ●   ●   ●
●   O   ●   ●

等等……

顺便说一句，这个例子(pic.1)的结果是 4。这意味着至少需要 4 个步骤才能将所有开关更改为 OFF。

我已经使用 javascript 实现了这个问题并将其提交到 github。

enter link description here

Answer 1

提供第一手解决方案

发布示例代码的链接很好，但您应该引用它，然后提供初步解决方案。解释您遇到问题的原因或遇到的问题。

算法和棋盘状态

您的目标是找到一条路径，在该路径中切换单元格会导致获胜状态。我看到您编写了一个可玩版本，但没有自动搜索逻辑。

看看A* search一些提示。除了尝试例程之外，您还需要一种比较棋盘状态的方法。您知道您是否已达到获胜条件，但搜索算法也往往需要启发式算法。您可以使用“引脚越少越好”的启发式方法开始。