1

任意の長さの 6 つの弦が与えられます。単語は以下のパターンで配置されます。縦にも横にも配置できます。

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

パターンは対称である必要はなく、図のように 2 つの空の領域が必要です。例えば：

与えられた文字列 

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

複数のパターンが可能な場合は、辞書編集的に最小の最初の行、次に 2 番目の行などのパターンが形成されます。これを解決するためにどのようなアルゴリズムを使用できますか?

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

このことから、上記の不等式により、2 つの最短の文字列が中間の文字列になることはできないことがわかります。

3 つの最大の文字列を等しくすることもできません。3 つの文字列のいずれかを中央の文字列として選択した後、等しい最大の 2 つの文字列が残るため、上記の不等式によると不可能です。

長さが規則的である場合にのみ、パズルはトリッキーになります。長さが不規則な場合は、長さから位置への直接マッピングを行うことができます。

上記の不等式により、2 つの最大の文字列が等しい場合、それらは中央の 2 つの文字列になります。これの最悪のケースは、長さ a、b、c、d が等しい「通常の」パズルです。

2 つの最大の文字列が等しくない場合、最大の文字列の位置はすぐに決定できます (その長さはパズル内で一意であるため) - 中央の文字列の 1 つとして。最悪の場合、もう一方の中間文字列の候補が 3 つある可能性があります。力ずくでそれらすべてをチェックしてください。

アルゴリズム：

  • 一意の長さの文字列を位置にマップしてみてください。
  • 真ん中の 2 つの文字列をブルート フォースで (前述のことを考慮して) 残りを埋めるためにブルート フォースを使用します。

馬鹿力総当たりでもたったの6本！= 720 ケース、文字列が左から右、上から下にしか移動できない場合 (反転なし)。文字列が任意の方向にあることが許可されている場合、46080 ケース (* 2^6) になります。

于 2013-02-07T20:55:37.363 に答える