2

「アムドックス」が主催する最近のコンテストで、私は次の質問に出くわしました:(質問の基本的な考え方）

固定サイズの12x12の行列が与えられます。長さ6、5、5、4、3、2の6つの線分が与えられます。マトリックスには空のスペースと塗りつぶされたスペースがあります。6つの線分すべてを同時にマトリックスに収めることができるかどうかにかかわらず、「はい」または「いいえ」を返す必要があります。線は水平または垂直にのみ配置できます。

この問題を解決するには、どのアルゴリズムを使用する必要がありますか？梱包 ？ナップザック？

4

3 に答える 3

5

問題をSATにマッピングし、SATソルバーを使用します。かなり自然なマッピングがあります。変数を定義します。

x_s_i_j_d = segment s starts at coordinates (i,j) and goes in direction d

（dは「右」または「下」です）

まず、すべてのセグメントと開始位置を反復処理し、開始マトリックスが与えられたときにどれが実行可能かを確認します。例、M：

000000000000
111111111111
...

セグメント1の長さが2の場合L_seg1_0_0_down = false、塗りつぶされたスペースにヒットするため、。

次に、2つの交差するセグメントを禁止する句を記述します。セグメント1とセグメント2の両方が長さ2の場合、次の句を追加します。

(!L_seg1_0_0_right || !L_seg2_1_0_right)

セグメント1が座標（0,0）と（1,0）を使用している場合、セグメント2は（1,0）も使用できないためです。

最後に、各セグメントを少なくとも1回使用する必要があるという条件を追加します。

(L_seg1_0_0_right || L_seg1_0_1_right || ...)

seg1が行くことができるすべての位置のために。次に、お気に入りのSATソルバーをそれに投げます。

于 2012-08-23T20:52:50.820 に答える
0

I would use a greedy fill algorithm such as the following:

for largest_line to smallest_line do
  for first_empty_square_in_matrix to last_empty_square_in_matrix do
    if line_fits_horizontal then
      place_line
      break
    else if_line_fits_vertical then
      place_line
      break
if all_lines_placed then
  write('Yes')
else
  write('No')

To optimise the above you might note that if a horizontal line of length n fails to fit at position (i,j) then you won't need to test for it fitting horizontally at any of (i+1,j),(i+2,j)...(i+n,j).

于 2012-08-23T20:55:48.563 に答える
0

アイデア:
すべての 2D 配列ポイントを反復処理し、使用可能なセグメントのコレクションを作成します。各ステップで、i-1 セルと j-1 セルを分析し、そのセルを含むセグメントがある場合は、それらの長さを増やします (明らかに、最大で 2 つのセグメントを見つけることができます)。
その後、配列を使用可能なセグメントに配置する必要があるため、挿入するたびに残りのすべてのセグメントを分析し、それらのいずれかが現在挿入されているセグメントと交差する場合は、サイズを小さくするか、2 つに分割する必要があります。

于 2012-08-23T22:39:34.613 に答える