gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:14:04 25 4
gpt4 key购买 nike

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

有一个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

最佳答案

提供第一手解决方案

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

算法和棋盘状态

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

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

关于algorithm - 一道关于开关控制的算法题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52152865/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com