1

给定 6 个任意长度的字符串。单词将按如下所示的模式排列。它们可以垂直或水平排列。

      --------
      |      |
      |      |
      |      |
      ---------------
             |      |
             |      |
             |      |
             --------

图案不必是对称的，并且需要有两个空白区域，如图所示。例如：

给定字符串 

PQF  
DCC  
ACTF  
CKTYCA  
PGYVQP  
DWTP

图案可以是 

DCC...  
W.K...  
T.T...  
PGYVQP  
..C..Q  
..ACTF

其中点代表空白区域。

另一个例子是 

RVE  
LAPAHFUIK  
BIRRE  
KZGLPFQR  
LLHU  
UUZZSQHILWB

模式是 

LLHU....  
A..U....   
P..Z....  
A..Z....  
H..S....  
F..Q....  
U..H....  
I..I....  
KZGLPFQR  
...W...V  
...BIRRE

如果可能有多个模式，则将形成具有字典顺序最小的第一行的模式，然后形成第二行，依此类推。有什么算法可以解决这个问题？

4

2 回答 2

1

查找适合此约束的字符串：

strlen(a) + strlen(b) - 1 = strlen(c)
strlen(d) + strlen(e) - 1 = strlen(f)

之后尝试所有可能的情况，如果它们是有效的。例如;

aaa.....
d.f.....
d.f.....
d.f.....
cccccccc
..f....e
..f....e
..bbbbbb

会有2*2*2 = 8不同的情况。

于 2013-02-07T19:57:45.327 回答
0

您可以应用许多启发式方法，但在此之前，让我们回顾一下拼图的一些属性。

+aa+
c  f
+ee+eee+
   f   d
   +bbb+

让我们用与上图中出现的相同字符来调用字符串的长度。我们有：

a + b - 1 = e
c + d - 1 = f

我将把中间交叉的 2 根弦称为中间弦。

我们也推断出字符串的长度不能小于2。因此，我们可以推断：

e > a, e > b
f > c, f > d

由此，我们知道由于上面的不等式，两个最短的字符串不可能是中间字符串。

最大的 3 个字符串也不可能相等，因为在选择 3 个字符串中的任何一个作为中间字符串后，我们剩下 2 个最大的字符串相等，根据上面的不等式是不可能的。

只有当长度正常时，这个谜题才会变得棘手。当长度不规则时，可以直接从长度映射到位置。

如果我们有 2 个最大的字符串相等，由于上面的不等式，它们是 2 个中间字符串。最坏的情况是“常规”拼图，其中长度 a、b、c、d 相等。

如果两个最大的字符串不相等，则可以立即确定最大字符串的位置（因为它的长度在拼图中是唯一的） - 作为中间字符串之一。在最坏的情况下，另一个中间字符串可能有 3 个候选者 - 只是蛮力并检查所有这些。

算法：

  • 尝试将唯一长度字符串映射到该位置。
  • 蛮力在中间的 2 个字符串（考虑到我上面提到的），蛮力填充其余的。

即使用愚蠢的蛮力，也只有6个！= 720 例，如果字符串只能从左到右，从上到下（不能反向）。如果允许字符串在任何方向上，将有 46080 个案例 (* 2^6)。

于 2013-02-07T20:55:37.363 回答