查找所有填充有 0 的矩形 · GeeksForGeeks 中文系列教程

# 查找所有填充有 0 的矩形 > 原文： [https://www.geeksforgeeks.org/find-rectangles-filled-0/](https://www.geeksforgeeks.org/find-rectangles-filled-0/) 我們有一個 2D 數組，其中填充了零和一。我們必須找到所有填充為 0 的矩形的起點和終點。假定矩形是分開的并且彼此不接觸，但是它們可以接觸數組的邊界。一個矩形可能只包含一個元素。例子： ``` input = [ [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1] ] Output: [ [2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5] ] Explanation: We have three rectangles here, starting from (2, 3), (3, 1), (5, 3) Input = [ [1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 0] ] Output: [ [0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5], [3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2], [7, 6, 7, 6] ] ``` 步驟 1：按行和列查找 0 第 2 步：遇到任何 0 時，將其位置保存在輸出數組中，并使用循環以任何公共數字更改與此位置相關的所有 0，以便我們下次可以將其排除在外。步驟 3：在步驟 2 中更改所有相關的 0 時，將最后處理的 0 的位置存儲在同一索引的輸出數組中。第 4 步：觸摸邊緣時要特別小心，不要減去-1，因為循環在確切的位置上已經斷開。下面是上述方法的實現： ``` # Python program to find all? # rectangles filled with 0 def findend(i,j,a,output,index): ????x = len(a) ????y = len(a[0]) ????# flag to check column edge case, ????# initializing with 0 ????flagc = 0 ????# flag to check row edge case, ????# initializing with 0 ????flagr = 0 ????for m in range(i,x):? ????????# loop breaks where first 1 encounters ????????if a[m][j] == 1:? ????????????flagr = 1 # set the flag ????????????break ????????# pass because already processed ????????if a[m][j] == 5:? ????????????pass ????????for n in range(j, y):? ????????????# loop breaks where first 1 encounters ????????????if a[m][n] == 1: ????????????????flagc = 1 # set the flag ????????????????break ????????????# fill rectangle elements with any ????????????# number so that we can exclude ????????????# next time ????????????a[m][n] = 5 ????if flagr == 1: ????????output[index].append( m-1) ????else: ????????# when end point touch the boundary ????????output[index].append(m)? ????if flagc == 1: ????????output[index].append(n-1) ????else: ????????# when end point touch the boundary ????????output[index].append(n)? def get_rectangle_coordinates(a): ????# retrieving the column size of array ????size_of_array = len(a)? ????# output array where we are going ????# to store our output? ????output = []? ????# It will be used for storing start ????# and end location in the same index ????index = -1 ????for i in range(0,size_of_array): ????????for j in range(0, len(a[0])): ????????????if a[i][j] == 0: ????????????????# storing initial position? ????????????????# of rectangle ????????????????output.append([i, j])? ????????????????# will be used for the? ????????????????# last position ????????????????index = index + 1???????? ????????????????findend(i, j, a, output, index)? ????print (output) # driver code tests = [ ????????????[1, 1, 1, 1, 1, 1, 1], ????????????[1, 1, 1, 1, 1, 1, 1], ????????????[1, 1, 1, 0, 0, 0, 1], ????????????[1, 0, 1, 0, 0, 0, 1], ????????????[1, 0, 1, 1, 1, 1, 1], ????????????[1, 0, 1, 0, 0, 0, 0], ????????????[1, 1, 1, 0, 0, 0, 1], ????????????[1, 1, 1, 1, 1, 1, 1] ????????] get_rectangle_coordinates(tests) ``` 輸出： ``` [[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]] ``` 本文由 [**Prabhat jha**](https://auth.geeksforgeeks.org/profile.php?user=Prabhat jha) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。 In 問 * * * * * *