ব্যাঙ্কিন পাইথনে একজন গার্ড থেকে সবচেয়ে কম দূরত্ব খুঁজুন

ধরুন আমাদের একটি ম্যাট্রিক্স আছে যা তিনটি অক্ষর 'O', 'G', এবং 'W' দিয়ে পূর্ণ যেখানে 'O' খোলা জায়গার প্রতিনিধিত্ব করছে, 'G' রক্ষীদের প্রতিনিধিত্ব করছে এবং 'ডব্লিউ' একটি ব্যাঙ্কের দেয়ালের প্রতিনিধিত্ব করছে, আমাদেরকে ম্যাট্রিক্সের সমস্ত O-কে প্রতিস্থাপন করতে হবে একটি গার্ড থেকে তাদের সবচেয়ে কম দূরত্বের ক্ষেত্রে, আমরা কোনো দেয়ালের মধ্য দিয়ে যেতে পারি না। আউটপুট ম্যাট্রিক্স গার্ড 0 দিয়ে প্রতিস্থাপিত হয় এবং দেয়াল -1 দ্বারা প্রতিস্থাপিত হয়।

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

তারপর আউটপুট হবে

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

• M :=5

• N :=5

• dir_row :=[-1, 0, 1, 0]

• dir_col :=[0, 1, 0, -1]

• একটি ফাংশন সংজ্ঞায়িত করুন is_ok()। এটি i, j

  লাগবে

• যদি (i রেঞ্জ 0 এবং M) অথবা (j রেঞ্জ 0 এবং j N), তাহলে

  • রিটার্ন ফলস

• রিটার্ন ট্রু

• একটি ফাংশন isSafe() সংজ্ঞায়িত করুন। এটি i, j,matrix, ফলাফল

  নেবে

• যদি ম্যাট্রিক্স[i, j] 'O' না হয় বা ফলাফল [i, j] -1 না হয়, তাহলে

  • রিটার্ন ফলস

• রিটার্ন ট্রু

• একটি ফাংশন calculate_dist() সংজ্ঞায়িত করুন। এটি ম্যাট্রিক্স গ্রহণ করবে

• ফলাফল :=ক্রম M x N এর একটি ম্যাট্রিক্স তৈরি করুন এবং -1

  দিয়ে পূরণ করুন

• একটি ডবল শেষ সারি q

  সংজ্ঞায়িত করুন

• 0 থেকে M রেঞ্জের জন্য, করুন

  • 0 থেকে N রেঞ্জে j-এর জন্য, করুন

    • ফলাফল[i, j] :=-1

    • যদি ম্যাট্রিক্স[i, j] 'G' এর মত হয়, তাহলে

      • pos :=[i, j, 0]

      • q

        এর বাম দিকে pos সন্নিবেশ করুন

      • ফলাফল[i, j] :=0

• যখন q> 0 এর মাপ অ-শূন্য, কর

  • curr :=q

    থেকে শেষ উপাদান মুছুন

  • x, y, dist :=curr[0], curr[1], curr[2]

  • 0 থেকে 3 রেঞ্জের জন্য, করুন

    • যদি is_ok(x + dir_row[i], y + dir_col[i]) হয় অ-শূন্য এবং isSafe(x + dir_row[i], y + dir_col[i], ম্যাট্রিক্স, ফলাফল) অ-শূন্য হয়, তাহলে

      • ফলাফল[x + dir_row[i], y + dir_col[i]] :=dist + 1

      • pos :=[x + dir_row[i], y + dir_col[i], dist + 1]

      • q

        এর বাম দিকে pos সন্নিবেশ করুন

• 0 থেকে M রেঞ্জের জন্য, করুন

  • 0 থেকে N রেঞ্জে j-এর জন্য, করুন

    • প্রদর্শন ফলাফল [i, j]

  • পরবর্তী লাইনে যান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from collections import deque as queue
M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]
def is_ok(i, j):
   if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)):
      return False
   return True
def isSafe(i, j,matrix, result):
   if (matrix[i][j] != 'O' or result[i][j] != -1):
      return False
   return True
def calculate_dist(matrix):
   result = [[ -1 for i in range(N)]for i in range(M)]
   q = queue()
   for i in range(M):
      for j in range(N):
         result[i][j] = -1
         if (matrix[i][j] == 'G'):
            pos = [i, j, 0]
            q.appendleft(pos)
            result[i][j] = 0
   while (len(q) > 0):
      curr = q.pop()
      x, y, dist = curr[0], curr[1], curr[2]
   for i in range(4):
      if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1
      pos = [x + dir_row[i], y + dir_col[i], dist + 1]
      q.appendleft(pos)
   for i in range(M):
      for j in range(N):
         if result[i][j] > 0:
            print(result[i][j], end=" ")
         else:
            print(result[i][j],end=" ")
      print()

matrix = [['O', 'O', 'O', 'O', 'G'],
   ['O', 'O', 'O', 'W', 'O'],
   ['O', 'W', 'O', 'O', 'O'],
   ['G', 'W', 'W', 'W', 'O'],
   ['O', 'O', 'O', 'O', 'G']]

calculate_dist(matrix)

ইনপুট

[['O', 'O', 'O', 'O', 'G'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'O', 'O', 'O'],
['G', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'O', 'G']]

আউটপুট

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0