算法 : Rearrange 2D Matrix (through element 'flipping' )

Question

我想知道一种算法(有效地)解决以下问题:数字 [1..9] 的二维矩阵需要从顶部 (1) 到底部 (9) 在水平线上对齐，但只能通过翻转用另一个数字垂直或水平。

示例输入矩阵:

1 8 2 6 1 6
9 2 5 1 6 2
3 6 9 2 9 8
5 1 7 4 2 8
4 2 7 6 9 5

期望的输出矩阵:

1 1 1 1 2 2
2 2 2 2 3 4
4 5 5 5 6 6
6 6 6 7 7 8
8 8 9 9 9 9

关于“翻转”的说明:以输入矩阵为例。左上角有一个“1”。那个 1 可以水平翻转它旁边的 8(第一行现在变成 8 1 2 6 1 6 )或者垂直翻转它下面的 9(第一列现在变成 9 1 3 5 4)。它不能与 2 对角翻转。

这个问题有什么解决方案(任何语言都可以)？

Answer 1

不错的拼图!无论如何，您可以尝试修改版本的排序算法。我不太擅长实现，但我可以稍后再给你一个。解决这个问题的另一种方法是通过 A* 算法。这是人工智能中使用的一种路径搜索算法，但我已经看到它适用于与此类似的问题。