मान लीजिए हमारे पास एक 2D मैट्रिक्स है जो एक जंगल को दर्शाता है जहां तीन प्रकार के सेल हैं: 0 खाली सेल, 1 पेड़ सेल, 2 जलता हुआ पेड़ सेल। हर दिन, एक पेड़ आग पकड़ लेता है जब उसके आसन्न (ऊपर, नीचे, बाएं, दाएं, विकर्ण नहीं) पेड़ में आग लगी हो। हमें वह दिनों की संख्या ढूंढनी है जो हर पेड़ को जलाने में लगेगी। यदि यह संभव नहीं है तो -1 लौटाएं।
उदाहरण के लिए, यदि इनपुट इस तरह है:
| 1 | 2 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
तो आउटपुट 4 होगा।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- ans := 0
- twos := एक नई सूची
- i को 0 से मैट्रिक्स की पंक्ति संख्या तक के लिए, करें
- j को 0 से मैट्रिक्स की स्तंभ संख्या तक के लिए, करें
- यदि matrix[i, j] 2 के समान है, तो
- जोड़ी (i, j) को twos के अंत में डालें
- जब तक twos खाली नहीं है, करें
- temp := एक नई सूची
- प्रत्येक जोड़ी (i, j) के लिए twos में, करें
- प्रत्येक जोड़ी (x, y) के लिए [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)] में, करें
- यदि x और y मैट्रिक्स की सीमा में हैं और matrix[x, y] 1 है, तो
- जोड़ी (x, y) को temp के अंत में डालें
- यदि x और y मैट्रिक्स की सीमा में हैं और matrix[x, y] 1 है, तो
- प्रत्येक जोड़ी (x, y) के लिए [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)] में, करें
- प्रत्येक जोड़ी (i, j) के लिए temp में, करें
- matrix[i, j] := 2
- twos := temp
- ans := ans + (1 यदि twos खाली नहीं है अन्यथा 0)
- यदि matrix[i, j] 2 के समान है, तो
- j को 0 से मैट्रिक्स की स्तंभ संख्या तक के लिए, करें
- ones = मैट्रिक्स में 1 की गिनती
- ans लौटाएं यदि ones 0 है अन्यथा -1
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, matrix):
ans = 0
twos = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 2:
twos.append((i, j))
while twos:
temp = []
for i, j in twos:
for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == 1:
temp.append((x, y))
for i, j in temp:
matrix[i][j] = 2
twos = temp
ans += 1 if twos else 0
ones = sum(int(matrix[i][j] == 1) for i in range(len(matrix)) for j in range(len(matrix[0])))
return ans if ones == 0 else -1
ob = Solution()
matrix = [
[1, 2, 1],
[1, 0, 1],
[1, 1, 1]
]
print(ob.solve(matrix))
इनपुट
matrix = [
[1, 2, 1],
[1, 0, 1],
[1, 1, 1]
]
आउटपुट
4