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

ধরুন আমাদের একটি 2D ম্যাট্রিক্স রয়েছে যেখানে এই মানগুলি উপস্থিত রয়েছে:0 একটি খালি ঘরকে উপস্থাপন করে। 1 একটি প্রাচীর প্রতিনিধিত্ব করে। 2 একজন ব্যক্তির প্রতিনিধিত্ব করে। এখন একজন ব্যক্তি উপরে, নীচে, বাম, ডান এই চারটি দিকের যে কোনও একটিতে হাঁটতে পারে অন্যথায় এক সময়ের ইউনিটে থাকতে পারে। আমাদের এমন একটি হাঁটার যোগ্য সেল খুঁজে বের করতে হবে যাতে এটি প্রত্যেকের সাথে দেখা করতে এবং সময় ফেরাতে যে সময় লাগবে তা কমিয়ে দেয়। আমাদের মনে রাখতে হবে যে একই খালি কক্ষের মধ্য দিয়ে দু'জন মানুষ হাঁটতে পারে এবং আপনি ধরে নিতে পারেন যে কোনও দুটি মানুষের মধ্যে সর্বদা কিছু পথ থাকে৷

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

তাহলে আউটপুট হবে 2, কারণ সকলেই পজিশন ম্যাট্রিক্স[1, 1]-এ সর্বাধিক 2টি ধাপের সাথে মিলিত হতে পারে।

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

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

• একটি ফাংশন bfs() সংজ্ঞায়িত করুন। এটি r, c

  লাগবে

• সারি :=একটি সারি নির্ধারণ করুন এবং এতে একটি জোড়া (r, c) সন্নিবেশ করুন

• dist :=কী মান জোড়া {(r, c):0}

  সহ একটি মানচিত্র

• সারিতে থাকা প্রতিটি জোড়া (r, c) এর জন্য করুন

  • যদি dist[r, c]> 15 অ-শূন্য হয়, তাহলে

    • লুপ থেকে বেরিয়ে আসুন

  • প্রতিটি প্রতিবেশীর জন্য (nr, nc) (r, c), do

    • যদি (nr, nc) dist-এ না থাকে, তাহলে

      • dist[nr, nc] :=dist[r, c] + 1

      • সারির শেষে সন্নিবেশ করুন (nr, nc)

  • প্রত্যাবর্তন জেলা

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• dist :=শূন্য

• প্রতিটি সারি সংখ্যা r এবং A এর সংশ্লিষ্ট সারির উপাদানগুলির জন্য করুন

  • প্রতিটি কলাম সংখ্যা c এবং সারি [c] val এর মানের জন্য, do

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

      • ndist :=bfs(r, c)

      • যদি dist নাল হয়, তাহলে

        • dist :=ndist

      • অন্যথায়,

        • dist-এর কীগুলির প্রতিটি কী-এর জন্য, করুন

          • যদি কীটি ndist-এ থাকে, তাহলে

            • dist[key] :=সর্বাধিক dist[key], ndist[key]

          • অন্যথায়,

            • dist[কী]

              সরান

• dist খালি না থাকলে ন্যূনতম সমস্ত মান ফেরত দিন, অন্যথায় 0 ফেরত দিন

উদাহরণ

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