C/C++矩阵算法

Question

我有一个矩阵，看起来像这样（它旁边的字母和数字索引）：

A B C 
1 {2, 0, 2} 
2 {1, 0, 1} 

几个条款将在问题中使用：

A 对是一对字母和数字。这个数字总是第一位。每一对基本上都是一个元素的索引。 （例如，1A = 2,2B = 0,1C = 2等）。

A 指令是一对两对。 “语法”是[sourcePair] [destinationpair]。 sourcePair总是必须是非零值，而目的地对话必须始终为零值。这当然也会阻止您使用与sourcePair和destinationPair相同的对。它的工作原理是这样的：任何值是在sourcePair（1或2）将移动到destinationPair然后sourcePair将（它将修改矩阵）设定为0。 （例如，1A1B→1B = 2,1A = 0; 1C2B→2B = 2,1C = 0等）。

A 密钥是一组16个命令（共64个字符）。

目标：要找到所有的关键，这将使矩阵看起来像这样可能的组合：

A B C 
1 {1, 0, 1} 
2 {2, 0, 2} 

矩阵的行基本上交换。算法不一定非常高效，因为我只会在用户按下按钮时打印按键。此外，密钥必须是长的（64个字符），长度为，长度为。例如，如果使用第一个x命令来执行某些操作，只占用一些空间，然后使用y命令来执行实际操作，则无关紧要。

一个实际的例子是：

1A3B3C1A1C3C3A1C3B3A1A3B3C1A1C3C3A1C3B3A3C3B1A3C3A1A1C3A3B1B1B1C - 我发现这个一个由手（笔和纸）。前5个命令使它看起来像所需的矩阵，然后接下来的5个命令是相同的（将其恢复到原始状态），然后接下来的6个命令（我通过稍微修改它来扩展5个命令交换并添加一个redudant命令）再次使它成为所需的矩阵。

感谢您的阅读，

Tuntuni。

Answer 1

这是一个图搜索问题。考虑矩阵的每个状态是图中的一个节点，合法命令是出站边。然后您会查找连接两个特定节点的所有路径。

深度有界广度优先搜索是然后穷尽搜索这个空间的所有路径的一种方法。

人们可以通过认识到所有路径可以通过首先与包含不循环的所有路径开始，然后插入循环行走直到击中所期望的长度来延伸过该溶液。这里的诀窍是所有周期的集合都可以进行预先计算和索引，从而可以将原始BFS限制为不重复节点的路径（这将快得多）。