algorithm - 减少回溯算法的时间

Question

我正在尝试使用回溯法解决问题。考虑到 n * n array(arr) 的出现，并且 n <= 20，我必须使用回溯。我应该在没有按下所有按钮的情况下制作给定的形状。我可能有多个答案，但我应该以您按下按钮的最少次数打印答案。

按下按钮会更改按下的按钮和上、下、左、右按钮的状态。 # 不是按下按钮，O 是按下按钮

例如，
4
哦哦哦哦
哦哦哦哦
哦哦哦哦
哦哦哦哦
作为输入给出

#O##
###哦
哦###
##O#
应该输出。

这意味着您可以通过四个操作(将按钮推到 O 位置)来制作输入给定的形状。

如果 n 为 20，在最坏的情况下，我的源代码将花费大约 1 分钟。
有什么方法可以减少花费的时间吗？

但我不知道该怎么做。

我目前使用的无希望条件是 arr[row-1][col] 和 temarr[row-1][col] 不是在 temans[row][col] 处操作按钮时也是如此。这是因为我无法在该位置之后更改 temarr [row-1] [col] 的外观。

开始:
1,1 位置的按钮: p np
按钮在 1,2 位置:p np p np
...
按钮在 i,j 位置:p np...p np
按钮在n,n位置:p np...p np

我通过在树形的特定位置显示所有按下(p)和未按下(np)按钮的情况来解决这个问题。

我解决了这个问题

Answer 1

Is there a way to reduce the time it takes?

在更好的计算机上运行它？开个玩笑^^。

看来你是学生，而且看起来真的像作业，所以我只是提供一些提示和线索。

• 假设在回溯的某个时刻，您“知道”(=计算)arr 和 temarr 之间有 35 个不同的值。您还知道 count - temcount == 3(如果您想找到更好的解决方案，可以只按 2 个按钮)。您找到更好解决方案的可能性有多大？
• compare 功能:假设我将 20*20 = 4,000 张扑克牌放在 table 上。数了30分钟，我知道1800个是“面朝上”，2200个是“面朝下”。现在我将 3 张牌从“面朝上”翻到“面朝下”，然后我将 2 张不同的牌翻过来。我是否必须花 30 分钟再次计数才能得到 2 个总数？
  回到您的案例:每次您修改 temarr 中的 5 个值时，您是否必须将其所有值与 arr 的值重新比较以测试它们是否不同？<
• 您当前计算 temarr 的唯一目的是将其与 arr 进行比较，并且您经常进行比较。您可以直接处理两个数组的“差异”:这意味着您有一个数组来判断哪个值是“正确”或“错误”。