এক ২D ম্যাট্রিক্স দেওয়া: ০=খালি সেল, ১=উত্তাল/ওয়াল, ২=মানুষ। মানুষ উপ-ডান-বাম-চাপে যেতে পারে। এমন একটি সেল (যেটি ওয়াল নয়) খুঁজতে হবে যাতে সব মানুষের ট্রাভেল দূরত্বের যোগফল ন্যূনতম হয়।
উদাহরণ: [[2,0,1,0],[1,0,1,2],[0,0,2,2]] → আউটপুট 7 (বেস্ট মিটিং পয়েন্ট: বটম-রাইট কর্নার)।
মাল্টি-সোর্স BFS সমাধান
- সব মানুষের লোকেশন (
2) খুঁজে বের করুন। - প্রতিটি মানুষের জন্য BFS চালিয়ে সেটি থেকে সব সেল পর্যন্ত দূরত্ব
costsম্যাট্রিক্সে স্টোর করুন। - প্রতিটি সেল (যেটি ওয়াল নয়) এর জন্য সব মানুষের দূরত্ব যোগ করুন।
- ন্যূনতম যোগফল বের করুন।
পাইথন কোড
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]*len(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 0 <= ni < len(matrix) and 0 <= 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 = sum(arr[i][j] for arr in costs.values())
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)) # 7
টাইম কমপ্লেক্সিটি: O(P × R × C) (P = মানুষের সংখ্যা, R×C = গ্রিড আকার)। বড় গ্রিডের জন্য অপ্টিমাইজেশন দরকার।
