Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में मैट्रिक्स उत्पन्न करने का प्रोग्राम जहां प्रत्येक सेल निकटतम 0 से मैनहट्टन दूरी रखता है


मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। हमें वही मैट्रिक्स ढूंढना है, लेकिन प्रत्येक सेल का मान निकटतम 0 से मैनहट्टन दूरी होगा। हम मान सकते हैं कि मैट्रिक्स में कम से कम एक 0 मौजूद है।

उदाहरण के लिए, यदि इनपुट है:

101
101
110

तो आउटपुट होगा:

101
101
210

क्योंकि केवल बॉटम-लेफ्ट सेल की निकटतम 0 से दूरी 2 है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (डायनामिक प्रोग्रामिंग - दो पास):

  • m := पंक्ति आकार, n := कॉलम आकार
  • पहला पास (टॉप-लेफ्ट से बॉटम-राइट):
    • प्रत्येक सेल के लिए, यदि मान 0 नहीं है तो इनफिनिटी सेट करें
    • ऊपर और बाएं पड़ोसी से न्यूनतम दूरी अपडेट करें
  • दूसरा पास (बॉटम-राइट से टॉप-लेफ्ट):
    • नीचे और दाएं पड़ोसी से न्यूनतम दूरी अपडेट करें
  • मैट्रिक्स लौटाएं

उदाहरण कोड

import math

class Solution:
    def solve(self, matrix):
        m, n = len(matrix), len(matrix[0])
        for y in range(m):
            for x in range(n):
                if matrix[y][x]:
                    matrix[y][x] = math.inf
        for y in range(m):
            for x in range(n):
                if y:
                    matrix[y][x] = min(matrix[y][x], matrix[y-1][x] + 1)
                if x:
                    matrix[y][x] = min(matrix[y][x], matrix[y][x-1] + 1)
        for y in range(m-1, -1, -1):
            for x in range(n-1, -1, -1):
                if y+1 < m:
                    matrix[y][x] = min(matrix[y][x], matrix[y+1][x] + 1)
                if x+1 < n:
                    matrix[y][x] = min(matrix[y][x], matrix[y][x+1] + 1)
        return matrix

ob = Solution()
matrix = [[1, 0, 1], [1, 0, 1], [1, 1, 0]]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

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

  1. - पायथन में प्रत्येक पंक्ति के तत्वों को फ्लिप करके अधिकतम योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है। दी गई मैट्रिक्स में किसी भी पंक्ति या स्तंभ के लिए हम सभी बिट्स को फ्लिप कर सकते हैं। यदि हम इन ऑपरेशनों को कितनी भी बार कर सकते हैं, और प्रत्येक पंक्ति को एक बाइनरी संख्या मानते हैं, तो हमें इन संख्याओं से बनने वाले सबसे बड़े योग को ढूंढना है। उदाहरण

  1. - पायथन में नेक्स्ट सेल मैट्रिक्स स्टेट का अगला स्टेट ढूंढने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है जहां 1 का अर्थ लाइव सेल है और 0 का अर्थ डेड सेल है। एक सेल के पड़ोसी उसके तत्काल क्षैतिज, ऊर्ध्वाधर और विकर्ण सेल हैं। हमें इन नियमों का उपयोग करके मैट्रिक्स का अगला स्टेट ढूंढना है दो या तीन जीवित पड़ोसियों वाला कोई भी जीवित सेल जीवित रहता है। तीन जीव

  1. - पायथन प्रोग्राम: दी गई स्ट्रिंग से सभी संभावित वैलिड IP एड्रेस जनरेट करना

    स्ट्रिंग दी गई है। स्ट्रिंग में केवल डिजिट्स हैं। हमारा कार्य सभी संभावित वैलिड IP एड्रेस कॉम्बिनेशन्स चेक करना है।यहां पहले हम स्ट्रिंग की लंबाई चेक करते हैं फिर . से स्प्लिट करते हैं। फिर हम . के विभिन्न कॉम्बिनेशन्स चेक करते हैं।उदाहरणInput: 255011123222 Its not a valid IP address. Input: 2550113