c++ - 给定 0 和 1 的二维数组，使用回溯找到其中的所有正方形

Question

在这个二维数组中，1代表一个点，0代表空白区域。例如这个数组:

1 0 0 0 1
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1

我的答案应该是2，因为像这样这个数组中有2个正方形(或长方形)

所有的点都要用上，不能再做一个正方形|矩形，如果它的所有点都已经被使用(就像我们不能从中间的点到右上角的点制作另一个正方形)因为它们都已经在其他正方形中使用，你可以多次使用任何点，如果至少有一个角是没有用到的。我可以将它作为一个实现问题来解决，但我不明白回溯与这个问题有何关系。提前致谢。

Answer 1

回溯，让我们看看你的问题的另一个可能的答案，你列出了:

• {0,0} 到 (2,1}
• {0,0} 到 {4,0}

作为一种解决方案另一种解决方案是(关于该点可以多次使用，只要一个点未被使用):

• {4,0} 到 {2,1}(第一次使用 4,0 和 2,1)
• {0,0} 到 {2,1}(第一次使用 0,0)
• {0,0} 到 {4,4}(第一次使用 4,4)

这是 3 步，通过回溯，它旨在使用递归向您显示替代结果。在这个等式中，如果您从数组的不同区域开始计算正方形的起始位置，您可以获得不同的结果。

例如，从 0,0 开始迭代，然后向右遍历每一行，试图找到所有以 [0,0] 开头的可能矩形，这将给出您提供的解决方案，从 4,0 开始迭代，向左遍历每个试图找到所有可能的解决方案的行将给出我的结果。