給定一個較大的二維矩陣，我可以唯一地擬合多少個尺寸較小的二維矩陣？

我有一個巨大的2D矩陣，代表3D遊戲的2D地形 - 牆壁和各種類型的地板（泥土，岩石等）。讓我們舉例說，有一個4x9的岩石地板面積。我需要在4x9空間的每個3x3區域的中心放置一個對象，並在解析和排除3x3區域後，在每個1x1區域放置一個對象。給定一個較大的二維矩陣，我可以唯一地擬合多少個尺寸較小的二維矩陣？

結果應該是放置3x3模板的3個對象和放置1x1模板的9個對象。

什麼是最有效的方法來實現這個算法？

來源

2013-02-11 S.Richmond

這是「製造變化」一2D版本？ – Mehrdad 2013-02-11 06:06:14

@BobMurphy：說實話，我真的很難從哪裏開始。在我的腦海中，我想我需要另一個矩陣來將單位標記爲「已使用」，例如，當我將它們作爲3x3模板的一部分時。但感覺凌亂。 – 2013-02-11 06:17:39

讓canPlace成爲BST座標。

for (x = 0:w) 
for (y = 0:h) 
    shouldPlace = true 
    for (x2 = -1:1) 
    for (y2 = -1:1) 
    if (grid[x+x2][y+y2].isObstruction()) 
     shouldPlace = false 
    if (shouldPlace) 
    canPlace.add((x,y))

上述複雜O(n^2 log n)

遞歸嘗試所有canPlace位置放置3x3的對象。

當你這樣做時，標記你放置它的區域被阻擋，並且在放置之前檢查是否阻塞。

以上覆雜度=？（更可能的名次使我們能夠找到一個解決方案很快）

for (x = 0:w) 
for (y = 0:h) 
    if (grid[x][y].isEmpty()) 
    place1x1(x, y)

以上覆雜= O(n^2)

總複雜= O(n^2 log n + ?)

來源

2013-02-11 06:19:32 Dukeling

這不會嘗試將2個3x3模板放置在例如3x4區域內，因爲它不排除現在使用的第一個3x3模板中的xy單元放置？或者你只是沒有在這裏顯示？ – 2013-02-11 06:30:23

@ S.Richmond編輯。 – Dukeling 2013-02-11 06:33:16

完美的感謝伴侶。 – 2013-02-11 06:48:52

給定一個較大的二維矩陣，我可以唯一地擬合多少個尺寸較小的二維矩陣？

回答

相關問題