मान लीजिए कि हमारे पास 2D मैट्रिक्स है, नीचे कुछ मान हैं -
-
0 एक खाली सेल का प्रतिनिधित्व करता है।
-
1 दीवार का प्रतिनिधित्व करता है।
-
2 एक व्यक्ति का प्रतिनिधित्व करता है।
यहां व्यक्ति इन चारों दिशाओं (ऊपर, नीचे, बाएं और दाएं) में से किसी एक पर चल सकता है। हमें एक ऐसी सेल ढूंढनी है जो दीवार न हो ताकि यह प्रत्येक व्यक्ति को चलने वाली कुल यात्रा दूरी को कम कर सके और अंत में दूरी का पता लगा सके।
तो, अगर इनपुट पसंद है
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
तो आउटपुट 7 होगा क्योंकि सबसे अच्छा मीटिंग पॉइंट निचला दायां कोना है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
दो:=एक नया नक्शा, लागत:=एक नया नक्शा
-
मैट्रिक्स में प्रत्येक अनुक्रमणिका i और पंक्ति r के लिए, करें
-
प्रत्येक अनुक्रमणिका j और r में मान v के लिए, करें
-
अगर v 2 के समान है, तो
-
दो [i, j] :=[i, j, 0]
-
लागत [i, j] :=दिए गए मैट्रिक्स के अनुसार आकार का 2D मैट्रिक्स बनाएं और अनंत से भरें
-
-
-
-
प्रत्येक कुंजी मान युग्म (k, q) के लिए दो में, करें
-
देखा :=एक नया सेट
-
जबकि q खाली नहीं है, करें
-
(i, j, लागत) :=q से पहला तत्व हटा दिया गया
-
अगर (i, j) दिख रहा है, तो
-
अगले पुनरावृत्ति के लिए जाएं
-
-
ऐड (i, j) इन सीन
-
लागत [के, आई, जे]:=लागत
-
प्रत्येक के लिए (di, dj) in ((1, 0), (−1, 0), (0, 1), (0, −1)), do
-
(नी, एनजे) :=(i + di, j + dj)
-
अगर नी और एनजे मैट्रिक्स की सीमा में हैं और मैट्रिक्स [नी, एनजे] 1 नहीं है, तो
-
q के अंत में (ni, nj, लागत + 1) डालें
-
-
-
-
-
उत्तर:=अनंत
-
मैं के लिए 0 से लेकर मैट्रिक्स की पंक्ति गणना तक, करें
-
j के लिए रेंज 0 से लेकर मैट्रिक्स की कॉलम काउंट तक, करें
-
cur_cost :=0
-
लागत के सभी मूल्यों की सूची में प्रत्येक गिरफ्तारी के लिए, करें
-
cur_cost :=cur_cost + arr[i, j]
-
-
उत्तर :=न्यूनतम उत्तर और cur_cost
-
-
-
वापसी उत्तर
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution:
def solve(self, matrix):
twos = {}
costs = {}
for i, r in enumerate(matrix):
for j, v in enumerate(r):
if v == 2:
twos[(i, j)] = [(i, j, 0)]
costs[(i, j)] = [[1e9 for _ in matrix[0]] for _
in matrix]
for k, q in twos.items():
seen = set()
while q:
i, j, cost = q.pop(0)
if (i, j) in seen:
continue
seen.add((i, j))
costs[k][i][j] = cost
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if (ni >= 0 and nj >= 0 and ni < len(matrix) and nj < len(matrix[0]) and matrix[ni][nj] != 1):
q.append((ni, nj, cost + 1))
ans = 1e9
for i in range(len(matrix)):
for j in range(len(matrix[0])):
cur_cost = 0
for arr in costs.values():
cur_cost += arr[i][j]
ans = min(ans, cur_cost)
return ans
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 1, 2],
[0, 0, 2, 2]
]
print(ob.solve(matrix)) इनपुट
matrix = [ [2, 0, 1, 0], [1, 0, 1, 2], [0, 0, 2, 2]]
आउटपुट
7
