পাইথনে সর্বাধিক দৈর্ঘ্যের সাপের ক্রম খুঁজুন

ধরুন আমাদের সংখ্যার একটি গ্রিড আছে; আমাদের একটি সাপের ক্রম খুঁজে বের করতে হবে এবং এটি ফিরিয়ে দিতে হবে। যদি একাধিক স্নেক সিকোয়েন্স থাকে, তাহলে শুধুমাত্র একটি রিটার্ন করুন। আমরা জানি যে গ্রিডের সংলগ্ন সংখ্যাগুলি ব্যবহার করে একটি সাপের ক্রম তৈরি করা হয় তাই প্রতিটি সংখ্যার জন্য, ডানদিকের সংখ্যা বা তার নীচের সংখ্যাটি হয় +1 বা -1 এর মান। সুতরাং, যদি বর্তমান মান গ্রিড কক্ষে থাকে (a, b), আমরা হয় ডানদিকে (a, b+1) যেতে পারি যদি সেই সংখ্যাটি ± 1 হয় অথবা নিচের দিকে যেতে পারি (a+1, b) যদি সেই সংখ্যা ± 1 হয়।

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

তাহলে আউটপুট হবে 6, ক্রম − 10 (0, 0) থেকে 9 (1, 0) থেকে 8 (1, 1) থেকে 7 (1, 2) থেকে 6 (1, 3) থেকে 7 (2, 3) থেকে 8 (3, 3)

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

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

  লাগবে

• পথ :=একটি নতুন তালিকা

• pt :=একটি বিন্দু [i, j]

• পাথের শেষে pt ঢোকান

• যখন গ্রিড[i, j] 0 নয়, do

  • যদি i> 0 এবং গ্রিড[i, j]-1 হয় গ্রিড[i-1, j] এর মতো, তাহলে

    • pt :=[i-1, j]

    • পাথের শেষে pt ঢোকান

    • i :=i - 1

  • অন্যথায় যখন j> 0 এবং গ্রিড[i, j]-1 গ্রিড[i, j-1] এর মতো হয়, তখন

    • pt :=[i, j-1]

    • পাথের শেষে pt ঢোকান

    • j :=j - 1

• ফেরার পথ

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

• lookup :=M x N আকারের একটি গ্রিড তৈরি করুন এবং 0

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

• length_max :=0, max_row :=0, max_col :=0

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

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

    • যদি i বা j অ-শূন্য হয়, তাহলে

      • যদি (i> 0 an এবং |গ্রিড[i-1, j] - গ্রিড[i, j]| 1 হয়, তাহলে

        • লুকআপ[i,j] =সর্বোচ্চ লুকআপ[i,j],লুকআপ[i-1,j] + 1)

        • যদি length_max

          • length_max :=লুকআপ[i, j]

          • max_row :=i

          • max_col :=j

      • যদি (j> 0 এবং |গ্রিড[i, j-1] - গ্রিড[i, j]| 1 হয়, তাহলে

        • যদি length_max

        • লুকআপ[i,j] =সর্বোচ্চ লুকআপ[i,j],lookup[i,j-1] + 1)

          • length_max :=লুকআপ[i, j]

          • max_row :=i

          • max_col :=j

• প্রদর্শনের দৈর্ঘ্য_সর্বোচ্চ

• পথ :=get_path(lookup, grid, max_row, max_col)

• পথের সমস্ত উপাদান বিপরীত ক্রমে প্রিন্ট করুন

উদাহরণ

আরও ভাল বোঝার জন্য আসুন আমরা নিম্নলিখিত বাস্তবায়ন দেখি &mius;

M =4N =4def get_path(grid, mat, i, j):path =list() pt =[i, j] path.append(pt) while (grid[i][j] !=0) :যদি (i> 0 এবং গ্রিড[i][j]-1 ==গ্রিড[i-1][j]):pt =[i-1, j] path.append(pt) i -=1 elif ( j> 0 এবং গ্রিড[i][j]-1 ==গ্রিড[i][j-1]):pt =[i, j-1] path.append(pt) j -=1 রিটার্ন pathdef get_sequence(গ্রিড ):lookup =[[0 for i range in range(N)] এর জন্য j in range(M)] length_max =0 max_row =0 max_col =0 in range(M):রেঞ্জে j এর জন্য(N):যদি ( i বা j):যদি (i> 0 এবং abs(গ্রিড[i-1][j] - গ্রিড[i][j]) ==1):lookup[i][j] =max(lookup[i] [j],lookup[i-1][j] + 1) if (length_max  0 এবং abs(গ্রিড[i][j-1] - গ্রিড[i][j]) ==1):lookup[i][j] =max(lookup[i][j],lookup[i ][j-1] + 1) যদি (দৈর্ঘ্য_ম্যাক্স <লুকআপ[i][j]):length_max =lookup[i][j] max_row =i max_col =j print("সর্বোচ্চ দৈর্ঘ্য:", length_max) পাথ =get_path (lookup, grid, max_row, max_col) প্রিন্ট("Sequence is:") ele এর বিপরীতে (পাথ):print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep ="")গ্রিড =[ [[10, 7, 6, 3], [9, 8, 7, 6], [8, 4, 2, 7] , [2, 2, 2, 8]]get_sequence(গ্রিড)

ইনপুট

[[10, 7, 6, 3],[9, 8, 7, 6],[8, 4, 2, 7],[2, 2, 2, 8]]

আউটপুট