Python - 0 से भरे सभी रेक्टेंगल ढूंढना

मान लीजिए हमारे पास एक बाइनरी 2D मैट्रिक्स है, अब हमें 0 से भरे सभी रेक्टेंगल्स के शुरुआती बिंदु और अंतिम बिंदु ढूंढने हैं। हमें ध्यान रखना है कि रेक्टेंगल्स अलग हैं और एक-दूसरे को नहीं छूते, हालांकि वे ऐरे बाउंड्री को छू सकते हैं। केवल एक एलिमेंट वाला रेक्टेंगल भी संभव है।

तो, यदि इनपुट इस तरह है:

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

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 के समान है, तो
  - output[index] के अंत में m-1 इन्सर्ट करें
- अन्यथा,
  - output[index] के अंत में m इन्सर्ट करें
- यदि flag_col, 1 के समान है, तो
  - output[index] के अंत में n-1 इन्सर्ट करें
- अन्यथा,
  - output[index] के अंत में n इन्सर्ट करें

मेन मेथड से, निम्नलिखित करें:

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(n):
        for j in range(len(a[0])):
            if a[i][j] == 0:
                op.append([i, j])
                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]]