在 Python 中查詢所有填充 0 的矩形

假設我們有一個二進位制二維矩陣，現在我們必須找到所有填充 0 的矩形的起點和終點。我們必須記住，矩形是分開的並且彼此不接觸，但是它們可以接觸陣列邊界。只有一個元素的矩形也是可能的。

因此，如果輸入類似於 -

1011101
1101111
1011001
1011001
1011011
1010000
1110001
1011101

那麼輸出將是 [[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

要解決此問題，我們將遵循以下步驟 -

  • 定義一個函式 find_rect()。這將接收 i、j、a、output 和 index 作為引數。
  • x := 行數
  • y := 列數
  • flag_col := 0
  • flag_row := 0
  • 對於 m 從 i 到 x 的範圍，執行以下操作：
    • 如果 a[m, j] 等於 1，則
      • flag_row := 1
      • 中斷
    • 如果 a[m, j] 等於 5，則
      • 不執行任何操作
    • 對於 n 從 j 到 y 的範圍，執行以下操作：
      • 如果 a[m, n] 等於 1，則
        • flag_col := 1
        • 中斷
      • a[m, n] := 5
    • 如果 flag_row 等於 1，則
      • 將 m-1 插入 output[index] 的末尾
    • 否則，
      • 將 m 插入 output[index] 的末尾
    • 如果 flag_col 等於 1，則
      • 將 n-1 插入 output[index] 的末尾
    • 否則，
      • 將 n 插入 output[index] 的末尾
  • 從主方法中，執行以下操作 -
  • n := a 的大小
  • op := 一個新的列表
  • idx := -1
  • 對於 i 從 0 到 n 的範圍，執行以下操作：
    • 對於 j 從 0 到 a[0] 的大小的範圍，執行以下操作：
      • 如果 a[i, j] 等於 0，則
        • 將 [i,j] 插入 op
        • idx := idx + 1
        • find_rect(i, j, a, op, idx)
  • 顯示 op

示例程式碼

讓我們看看以下實現以獲得更好的理解 -

即時演示

def find_rect(i,j,a,output,index):
   x = len(a)
   y = len(a[0])
   flag_col = 0
   flag_row = 0
   for m in range(i,x):
      if a[m][j] == 1:
         flag_row = 1
         break
      if a[m][j] == 5:
         pass
      for n in range(j, y):
         if a[m][n] == 1:
            flag_col = 1
            break
         a[m][n] = 5
   if flag_row == 1:
      output[index].append( m-1)
   else:
      output[index].append(m)
   if flag_col == 1:
      output[index].append(n-1)
   else:
      output[index].append(n)
def get_coord(a):
   n = len(a)
   op = []
   idx = -1
   for i in range(0,n):
      for j in range(0, len(a[0])):
         if a[i][j] == 0:
         op.append([i, j])
         idx = idx + 1
         find_rect(i, j, a, op, idx)
   print (op)
tests = [[1, 0, 1, 1, 1, 0, 1],
         [1, 1, 0, 1, 1, 1, 1],
         [1, 1, 1, 0, 0, 1, 1],
         [1, 0, 1, 1, 0, 0, 1],
         [1, 0, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 0, 1],
         [1, 0, 1, 1, 1, 0, 1]]
get_coord(tests)

輸入

[[1, 0, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1]]

輸出

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

更新於: 2020年8月28日

315 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告