在 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告