在Python中找到所有用0填充的矩形

假设我们有一个二进制2D矩阵，现在我们必须找到所有用0填充的矩形的起点和终点。我们必须牢记，矩形是分开的，彼此之间不接触，但是它们可以接触阵列边界。仅包含单个元素的矩形也是可能的。

所以，如果输入像-

那么输出将是[[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，输出，索引

• x：=行数

• y：=列数

• flag_col：= 0

• flag_row：= 0

• 对于范围i至x的m

• 在输出[索引]的末尾插入n

• 在输出[索引]的末尾插入n-1

• 在输出[索引]的末尾插入m

• 在输出[索引]的末尾插入m-1

• 如果a [m，n]等于1，则

• a [m，n]：= 5

• flag_col：= 1

• 打破

• 没做什么

• flag_row：= 1

• 打破

• 如果a [m，j]等于1，则

• 如果a [m，j]与5相同，则

• 对于j到y范围内的n

• 如果flag_row与1相同，则

• 除此以外，

• 如果flag_col与1相同，则

• 除此以外，

• 从主要方法中，执行以下操作-

• n：=一个的大小

• op：=一个新列表

• idx：= -1

• 对于0到n范围内的i，执行

• 如果a [i，j]等于0，则

• 将[i，j]插入op

• idx：= idx + 1

• find_rect(i,j,a,op,idx)

• 对于范围为0到a [0]大小的j，执行

• 显示操作

范例程式码 

让我们看下面的实现以更好地理解-

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]]