在二維陣列中尋找合適的切割片

Question

好吧，標題不太合適，請繼續閱讀（我無法獲得更好的）。

注意：使用Python 2.7，但算法也會有所幫助。

我正在製作側卷軸遊戲，其中我在飛行中產生障礙物。我遇到的麻煩是弄清楚如何產生障礙。 o_O
我有一種某種邏輯，但後來在計算整個邏輯時遇到了麻煩。

因此，這裏是從實現的角度來看我的問題：
我有一個Surface，其中我已經把一些Element s，這是所有的矩形。
認爲它像：

0 0 0 0 0 0 0 
0 0 0 0 1 1 0 
0 0 0 0 1 1 0 
0 0 0 0 1 1 0 
0 0 0 0 0 0 0 
0 1 1 0 0 1 1 
0 0 0 0 0 1 1 

如在上述結構中，我怎樣才能確定是否可以在不重疊的（1S）的另一個矩形被添加一個axb矩形，並且其中所有。此外，與所有其他對象保持x個元素（甚至對角線）的距離，這意味着整個矩形是（x + 3，x + 4）。就像如果x=1, a=3, b=4東西，只有一個可能的安排：
（2S代表了新的對象）

2 2 2 0 0 0 0 
2 2 2 0 1 1 0 
2 2 2 0 1 1 0 
2 2 2 0 1 1 0 
0 0 0 0 0 0 0 
0 1 1 0 0 1 1 
0 0 0 0 0 1 1 

基本上，我需要找到所有的點，從側面a和b的矩形可以有它，說，左上角。這是如何實現的？

注意：打開更好的想法，爲飛行中產生障礙！

PS：我已經問過這裏和程序員，因爲我認爲它落在這兩個網站上的主題。

Answer 1

下面應該工作得相當好：

def find_valid_locations(grid, z, a, b): 
    check = [(0, 0, 0, 0)] 
    w = z + b 
    h = z + a 
    while check: 
     x, y, ox, oy = check.pop() 
     if x + w >= len(grid) or y + h >= len(grid[0]): 
      continue 
     for i, row in enumerate(grid[x+ox:x+w+1], x+ox): 
      for j, val in enumerate(row[y+oy:y+h+1], y+oy): 
       if val: 
        break 
      else: 
       continue 
      check.append((x, j+1, 0, 0)) 
      if y == 0: 
       check.extend((ii, j+1, 0, 0) for ii in range(x+1, i+1)) 
       check.append((i+1, y, 0, 0)) 
      break 
     else: 
      yield (x, y) 
      check.append((x, y+1, 0, h-1)) 
      if y == 0: 
       check.append((x+1, y, w-1, 0)) 
      continue 

這裏的蠻力法將檢查每個潛在的矩形位置中的所有位置，並且只返回rectange沒有遇到非零位置的位置。實際上，這就是我們在這裏做，有以下優化：

• 如果我們已經找到了一個有效的位置（X，Y），我們可以檢查位置（X + 1，y）和（X，Y + 1 ），只需通過向下或向右移動來檢查添加到矩形的新位置。
• 如果我們在檢查位置（x，y）時在位置（i，j）遇到障礙，我們可以跳過檢查包含（i，j）的任何其他位置，方法是在（i + 1，y ）和（x，j + 1）。

注意，我改名參數x到z，這樣我可以使用x在代碼中的行索引。

Answer 2

您可以將面存儲在一個矩陣M，然後遍歷矩陣找個地方爲新的矩形R的左上角：

for all rows of matrix M 
    for all columns of matrix M 
     variable empty = 0 
     for all numbers from 1 to a 
      for all numbers from 1 to b 
       empty = empty + M(row + a, col + b)      
     if empty == 0 
      insert R(row,col) //insert R with top-left corner at M(row,col) 
      break;  

Answer 3

這是一個蠻力搜索，它考慮了在一個二維Python列表（列表列表）中的一個網格中，具有邊界c的矩形a，b的所有可能位置。

find_placements在調用isvalid之前將寬度添加到邊框和高度。這種方式isvalid不需要考慮邊界的任何事情。

我用寬度，高度，邊框的變量a, b, c，這樣它們就不會被通常爲x, y, z的座標所困惑。 gx和gy是網格x和網格y的縮寫。

一個差異在於，以這種方式用2維列表表示一個網格，訪問一個單元是用grid[y][x]而不是grid[x][y]完成的。其他一切都很簡單。

def find_placements(grid, a, b, c): 
    """ 
    Return [(x, y), ...] for all valid placements in the grid 
    of rectangle a x b with border c. 
    """ 
    result = [] 
    for gx in xrange(len(grid[0]) - (a + c)): 
     for gy in xrange(len(grid) - (b + c)): 
      if isvalid(grid, (a + c), (b + c), gx, gy): 
       result.append((gx, gy)) 
    return result 


def isvalid(grid, a, b, x, y): 
    """ 
    Return True if rect a, b fits at pos x, y 
    without overlapping. 
    """ 
    for gx in xrange(x + a): 
     for gy in xrange(y + b): 
      if grid[gy][gx]: 
       return False 
    return True 

---

>>> grid =[ 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 1, 0, 0, 1, 1], 
    [0, 0, 0, 0, 0, 1, 1] 
] 
>>> find_placements(grid, 3, 4, 1) 
[(0, 0)] 
>>>