ধরুন আমাদের কাছে R সারি এবং C কলাম সহ পূর্ণসংখ্যার একটি ম্যাট্রিক্স A আছে, আমাদের [0,0] থেকে শুরু করে [R-1,C-1] এ শেষ হওয়া একটি পথের সর্বাধিক স্কোর খুঁজে বের করতে হবে। এখানে স্কোরিং কৌশলটি সেই পথে সর্বনিম্ন মান হবে। উদাহরণস্বরূপ, পাথ 8 → 4 → 5 → 9 4 এর মান হল। একটি পাথ 4টি মূল দিকগুলির মধ্যে একটিতে একটি পরিদর্শন করা সেল থেকে যেকোনো প্রতিবেশী অনাদর্শিত কক্ষে (উত্তর, পূর্ব, পশ্চিম, দক্ষিণ) কয়েকবার সরে যায়। .
উদাহরণস্বরূপ, যদি গ্রিড −
এর মত হয়| 5 | 4 | 5 |
| 1 | 2 | 6 |
| 7 | 4 | ৷6 |
কমলা কোষের পথ হবে। আউটপুট হল 4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- r :=সারির সংখ্যা এবং c :=কলামের সংখ্যা
- উত্তর :=সর্বনিম্ন A[0, 0] এবং A[r – 1, c – 1]
- একটি ম্যাট্রিক্স তৈরি করুন যাকে বলা হয় ভিজিটড অফ অর্ডার A এর মতো, এবং এটি FALSE দিয়ে পূরণ করুন
- h :=একটি তালিকা, যেখানে আমরা একটি টিপল সংরক্ষণ করি (-A[0, 0], 0, 0)
- h থেকে গাদা তৈরি করুন
- যখন h খালি নয়
- v, x, y :=হিপ থেকে h মুছে দিন এবং তিনটি মান সংরক্ষণ করুন
- যদি x =r – 1 এবং y :=c – 1 হয়, তাহলে লুপ থেকে বেরিয়ে আসুন
- উত্তর :=উত্তরের মিনিট, A[x, y]
- পরিদর্শন করেছেন[x, y] :=সত্য
- তালিকায় dy, dx এর জন্য [(-1, 0), (1, 0), (0, 1), (0, -1)], do
- a :=x + dx এবং b :=y + dy
- যদি 0 থেকে r – 1 এর মধ্যে a এবং b রেঞ্জ 0 থেকে c – 1 এবং পরিদর্শন করা [a, b] মিথ্যা হয়,
- (-A[a, b], a, b) h সহ স্তূপে ঢোকান
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
import heapq
class Solution(object):
def maximumMinimumPath(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
r,c = len(A),len(A[0])
ans = min(A[0][0],A[-1][-1])
visited = [[False for i in range(c)] for j in range(r)]
h = [(-A[0][0],0,0)]
heapq.heapify(h)
while h:
# print(h)
v,x,y = heapq.heappop(h)
if x== r-1 and y == c-1:
break
ans = min(ans,A[x][y])
visited[x][y]= True
for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
a,b = x+dx,y+dy
if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
heapq.heappush(h,(-A[a][b],a,b))
return ans ইনপুট
[[5,4,5],[1,2,6],[7,4,6]]
আউটপুট
4
