3

2次元空間にNXMポイントのグリッドがあります。アイテムは、（x + 2、y-2）、（x-2、y-2）、または（x-2、y + 2）に別のアイテムがあってはならないように、ポイント（x、y）に配置できます。 ）または（x + 2、y + 2）。さらに、グリッド内に詰まっているポイントはほとんどありません。つまり、これらのポイントにアイテムを配置することはできません。

では、グリッドに配置できるアイテムの最大数を見つける方法。

4

3 に答える 3

0

より単純な1d問題を考えてみましょう。ブロックされたセルを持つ長さの配列が与えられた場合、に1がある場合、およびに1がないnように、セルを配置する方法はいくつありますか。xx - 2x + 2

これは冗長な条件であることに注意してください。に1がある場合、1がない場合はx十分ですx - 2（に1がある場合x + 2、この削減された条件が破られます）。

しましょうdp[i, j] = number of ways to populate 1 .. i with points such that the last element is j。

我々は持っています：

dp[i, 0] = dp[i - 1, 0] + dp[i - 1, 1] <- no 1 at i
dp[i, 1] = 2 * dp[i - 2, 0] <- we MUST have 0 at i - 2, but i - 1 can have whatever
=> if i is blocked dp[i, _] = dp[i - 1, _]

例：

n = 3
brute force solutions:
000
010
100
001
110
011
=> 6
dp[0, 0] = 1 dp[0, 1] = 0
dp[1, 0] = 1 dp[1, 1] = 1
dp[2, 0] = 2 dp[2, 1] = 2
dp[3, 0] = 4 dp[3, 1] = 2
=> dp[3, 0] + dp[3, 1] = 6

同じことがあなたの問題にも使われます。条件を「（x-2、y-2）および（x + 2、y-2）に点がない場合、（x、y）に点がある可能性がある」に減らすことができることに注意してください。次に、dpマトリックスを繰り返して入力しますO(lines*columns)。

于 2012-08-09T15:13:07.847 に答える
0

エッジケースを無視できるように、グリッドをトーラス、つまり側面を「ラップアラウンド」(上->下、左->右)と見なすことは説明に役立つと思います。N と M が大きい場合、これは良い近似です。

トーラスでは、各ポイントは必然的に他の 2 つのポイントの存在をブロックしますが、除外をオーバーラップさせることができます。つまり、1 つのポイント(x+2, y-2)は別のポイントのもの(x+2, y-2)です。したがって、達成できる最大のパッキングは 1/2 です。これは、2 つの完全な列、2 つの空の列、2 つの完全な列など、列のストライプを交互に配置することで実現できます。

コーナー ケース (M は 4 の倍数ではない) はそのままにします。

トーラスではないグリッドでは、2 つの考慮事項があります。最初に、完全な列をグリッドの端まで直接開始できます。また、下の 2 つの行を完全に埋めることもできます (「下」が最小の y です)。したがって、1/2 よりわずかに優れたパッキングを達成できますが、次元が無限に近づくと、それでも 1/2 になります。

于 2012-08-09T04:10:01.370 に答える
0

これらのブロッキング ポイントのない最適な充填は、カラムに配置することです。

(a + 0), (a + 3), (a + 6), ..., (a + 3*n)

これらの列の外にブロックが存在する場合は、改善できません。(x, y) の列にブロックが存在する場合、(x+2, y-2) と (x-2, y-2) にポイントを配置できます。したがって、すべての列に目を通し、列上のブロックの数を最小限に抑えるように配置してみてください。（これは前に最大化したと言ったことに注意してください。私も昨夜3時間眠りました）

これは n*m ステップで確認できます。

于 2012-08-09T03:48:38.927 に答える