मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। हमें एक ही मैट्रिक्स को खोजना होगा, लेकिन प्रत्येक सेल का मान मैनहट्टन दूरी से निकटतम 0 होगा। हम मान सकते हैं कि मैट्रिक्स में कम से कम एक 0 मौजूद है।
तो, अगर इनपुट पसंद है
1 | 0 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
तो आउटपुट होगा
1 | 0 | 1 |
1 | 0 | 1 |
2 | 1 | 0 |
क्योंकि केवल निचले बाएँ सेल में निकटतम 0 से 2 की दूरी है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- m:=मैट्रिक्स की पंक्ति का आकार, n:=मैट्रिक्स का स्तंभ आकार
- y के लिए 0 से m की सीमा में, करें
- 0 से n की श्रेणी में x के लिए, करें
- यदि मैट्रिक्स [y, x] शून्य नहीं है, तो
- मैट्रिक्स[y, x] :=अनंत
- यदि मैट्रिक्स [y, x] शून्य नहीं है, तो
- 0 से n की श्रेणी में x के लिए, करें
- y के लिए 0 से m की सीमा में, करें
- 0 से n की श्रेणी में x के लिए, करें
- यदि y शून्य नहीं है, तो
- मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y-1, x] + 1
- यदि x शून्य नहीं है, तो
- मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y, x - 1] + 1
- यदि y शून्य नहीं है, तो
- 0 से n की श्रेणी में x के लिए, करें
- y के लिए m - 1 से 0 की सीमा में, 1 से घटाएं
- x के लिए n - 1 से 0 की श्रेणी में, 1 से घटाएं
- यदि y + 1 <मी, तो
- मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y + 1, x] + 1
- यदि x + 1
- मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y, x + 1] + 1
- यदि y + 1 <मी, तो
- x के लिए n - 1 से 0 की श्रेणी में, 1 से घटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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]]