পাইথনের সমস্ত ব্যক্তির সাথে দেখা করার জন্য ন্যূনতম দূরত্ব খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে নিচের মত কিছু মান আছে −

• 0 একটি খালি ঘর প্রতিনিধিত্ব করে৷

• 1 একটি প্রাচীর প্রতিনিধিত্ব করে৷

• 2 একজন ব্যক্তির প্রতিনিধিত্ব করে।

এখানে একজন ব্যক্তি এই চারটি দিক (উপর, নিচে, বাম এবং ডান) যে কোনো একটিতে হাঁটতে পারে। আমাদের এমন একটি ঘর খুঁজে বের করতে হবে যা প্রাচীর নয় যাতে এটি প্রতিটি ব্যক্তিকে হেঁটে যেতে এবং অবশেষে দূরত্ব খুঁজে বের করতে মোট ভ্রমণ দূরত্বকে কমিয়ে দেয়৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 7 কারণ সর্বোত্তম মিটিং পয়েন্ট হল নীচের ডানদিকে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• twos :=একটি নতুন মানচিত্র, খরচ :=একটি নতুন মানচিত্র

• ম্যাট্রিক্সে প্রতিটি সূচক i এবং সারি r-এর জন্য করুন

  • প্রতিটি সূচী j এবং মান v এর জন্য r, করুন

    • যদি v 2 এর মত হয়, তাহলে

      • দুই[i, j] :=[i, j, 0]

      • খরচ[i, j] :=প্রদত্ত ম্যাট্রিক্সের মতো আকারের একটি 2D ম্যাট্রিক্স তৈরি করুন এবং অসীম দিয়ে পূরণ করুন

• প্রতিটি কী মান জোড়ার জন্য (k, q) দুইয়ে, করুন

  • দেখা হয়েছে :=একটি নতুন সেট

  • q খালি না থাকার সময়, করুন

    • (i, j, খরচ) :=q

      থেকে প্রথম উপাদান মুছে ফেলা হয়েছে

    • যদি (i, j) দেখা যায়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • দেখাতে যোগ করুন (i, j)

    • খরচ [k, i, j] :=খরচ

    • প্রতিটি (di, dj) এর জন্য ((1, 0), (−1, 0), (0, 1), (0, −1)), do

      • (ni, nj) :=(i + di, j + dj)

      • যদি ni এবং nj ম্যাট্রিক্সের পরিসরে থাকে এবং ম্যাট্রিক্স[ni, nj] 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