परिचय
मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां ये मान मौजूद हैं: 0 एक खाली सेल दर्शाता है। 1 एक दीवार दर्शाता है। 2 एक व्यक्ति दर्शाता है। अब एक व्यक्ति चार दिशाओं में से किसी में चल सकता है: ऊपर, नीचे, बाएं, दाएं या एक समय इकाई में स्थिर रह सकता है। हमें एक वॉकेबल सेल ढूंढना है जो सभी के मिलने में लगने वाले समय को न्यूनतम करता है और वह समय वापस करना है। ध्यान रखें कि दो लोग एक ही खाली सेल से चल सकते हैं और आप मान सकते हैं कि किन्हीं दो लोगों के बीच हमेशा कोई न कोई पथ होता है।
उदाहरण
| 2 | 0 | 1 | 0 |
| 1 | 0 | 0 | 2 |
| 2 | 0 | 2 | 0 |
तो आउटपुट 2 होगा, क्योंकि सभी matrix[1, 1] पर अधिकतम 2 चरणों में मिल सकते हैं।
समाधान दृष्टिकोण
प्रत्येक व्यक्ति से BFS चलाएं ताकि सभी पहुंच योग्य सेल्स तक की दूरी मिले। फिर प्रत्येक सेल के लिए, सभी व्यक्तियों की अधिकतम दूरी लें (सबसे धीमा व्यक्ति निर्धारित करता है)। सभी सेल्स में इस अधिकतम दूरी का न्यूनतम उत्तर है।
उदाहरण कोड
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def get_neighbor(r, c):
for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
yield nr, nc
def bfs(r, c):
queue = [(r, c)]
dist = {(r, c): 0}
for r, c in queue:
if dist[r, c] > 15:
break
for nr, nc in get_neighbor(r, c):
if (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return dist
dist = None
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 2:
ndist = bfs(r, c)
if dist is None:
dist = ndist
else:
for key in list(dist.keys()):
if key in ndist:
dist[key] = max(dist[key], ndist[key])
else:
del dist[key]
return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
print(ob.solve(matrix))
इनपुट
[
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
आउटपुट
2
निष्कर्ष
मल्टी-सोर्स BFS दृष्टिकोण सभी मीटिंग पॉइंट्स के लिए न्यूनतम अधिकतम दूरी ढूंढता है। समय जटिलता O(कुल_लोगों × R × C) है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
