मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। हमें वही मैट्रिक्स ढूंढना है, लेकिन प्रत्येक सेल का मान निकटतम 0 से मैनहट्टन दूरी होगा। हम मान सकते हैं कि मैट्रिक्स में कम से कम एक 0 मौजूद है।
उदाहरण के लिए, यदि इनपुट है:
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
तो आउटपुट होगा:
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
क्योंकि केवल बॉटम-लेफ्ट सेल की निकटतम 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]]