1929_算法设计例题：电路板排列问题（回溯）

最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是，将n块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。

设B = { 1, 2, …, n }是n块电路板的集合。集合L = { N₁ ，N₂ ，…，N_m }是n块电路板的m个连接块。其中每个连接块N_i是B的一个子集，且N_i中的电路板用同一根导线连接在一起。

例如，设n=8，m=5。给定n块电路板及其m个连接块如下：

B = { 1, 2, 3, 4, 5, 6, 7, 8 } ;   L = { N₁, N₂, N₃, N₄, N₅ }；

N₁ = { 4, 5, 6 } ;  N₂ = { 2, 3 } ;  N₃ = { 1, 3 } ;  N₄ = { 3, 6 } ; N₅ = { 7, 8 }。

这8块电路板的一个可能的排列如图所示。

在最小长度电路板排列问题中，连接块的长度是指该连接块中第1块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块N₄的第1块电路板在插槽3中，它的最后1块电路板在插槽6中，因此N₄的长度为3。同理 N₂的长度为2。图中连接块最大长度为3。

对于给定的电路板连接块，试设计一个回溯法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。

输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行有2 个正整数n 和m ( 1 ≤ m, n ≤ 12 )。接下来的n行中，每行有m个数。第k行的第j个数为0表示电路板k不在连接块j 中，1表示电路板k在连接块j中。

对应每个测试样例输出一行，格式为"Case #: W"，其中'#'表示第几个测试样例（从1开始计），W为电路板排列最小长度。

2
8 5
0 0 1 0 0
0 1 0 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 0 0
1 0 0 1 0
0 0 0 0 1
0 0 0 0 1
8 5
1 1 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 0 0 1

Case 1: 2
Case 2: 4