সর্বাধিক দৈর্ঘ্যের স্নেক ক্রম সন্ধান করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক কোডনেশন এক্সপিডিয়া ইয়ানডেক্স
ডায়নামিক প্রোগ্রামিং জরায়ু

"সর্বাধিক দৈর্ঘ্যের স্নেক ক্রম সন্ধান করুন" সমস্যাটি বলে যে আমাদের সাথে একটি সরবরাহ করা হয় গ্রিড ধারণকারী পূর্ণসংখ্যার। কাজটি সর্বাধিক দৈর্ঘ্যের সহিত সর্প সন্ধান করা find গ্রিডে 1 এর নিখুঁত পার্থক্যের সাথে সংলগ্ন সংখ্যাগুলির একটি ক্রম, একটি স্নেক ক্রম হিসাবে পরিচিত as একটি সংখ্যার সংলগ্ন উপাদানগুলি গ্রিডের মধ্যে বিদ্যমান বলে মনে করা হয় যে এটিগুলি বাম এবং প্রতিবেশীদের উপরে রয়েছে numbers সাধারণভাবে বলতে গেলে, আপনি যদি গ্রিডের (i, j) কক্ষে দাঁড়িয়ে থাকেন তবে কোষগুলি (i, j-1), (i-1, j) এর সংলগ্ন অবস্থার ভিত্তিতে যদি তারা গ্রিডের ভিতরে থাকে।

উদাহরণ

3 3// dimensions of grid
1 2 3
2 4 5
1 2 1
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

ব্যাখ্যা

সর্বাধিক দৈর্ঘ্যের স্নেক ক্রম সন্ধান করুন

অভিগমন

সমস্যাটি সর্বোচ্চ দৈর্ঘ্যের সাথে সাপের ক্রম সন্ধান করতে বলে এবং আমরা একটি ইনপুট হিসাবে গ্রিড সরবরাহ করি। গ্রিডের উপরের বাম দিকের কোণ থেকে একটি নিষ্পাপ বা হিংস্র ফোর্স পন্থা শুরু করা এবং পুনরাবৃত্তি ব্যবহার করে এটি তার ডান এবং নীচের প্রতিবেশীর মধ্য দিয়ে যায়। একইভাবে সেই ঘরগুলি থেকে তাদের প্রতিবেশীদের কাছে যান এবং ততক্ষণ আপনি এমন কোনও ঘর খুঁজে না পান যতক্ষণ না শর্ত আরোপিত শর্তগুলির কারণে সামনে এগিয়ে যাওয়া কোনও বিকল্প নয়। পুনরাবৃত্তি ব্যবহার করে যেখানে সাধারণভাবে আমাদের চারটি পুনরাবৃত্ত কল রয়েছে, সময় জটিলতা উচ্চতর দিকে চলে যাবে।

উপরোক্ত পদ্ধতির পরিবর্তে, আমরা সাথে যেতে পারি ডায়নামিক প্রোগ্রামিং কারণ আমরা একটি পুনরাবিপন্ন সমাধান ব্যবহার করে সমস্যাটি বর্ণনা করি। তারপরে সমাধানটিকে অনুকূলিত করার জন্য কেবল এটি মেমোজাইজ করুন। উপরোক্ত পদ্ধতির জন্য সময় জটিলতা হ'ল তাত্পর্যপূর্ণ তবে ব্যবহার গতিশীল প্রোগ্রামিং এটি বহুবর্ষে হ্রাস করতে পারে। এই সমস্যার জন্য, আমরা দুটি রাজ্যের দিকে নজর রাখব প্রথমে সারি সূচক এবং তারপরে কলাম সূচক। ডিপি টেবিলের প্রতিটি ঘর তার ঠিক উপরে এবং ঠিক বাম ঘরের উপর নির্ভর করবে। যদি আমাদেরও সেই উত্তরকোষের জন্য নির্বাচিত কক্ষগুলির প্রয়োজন হয়, তবে আমরা ডিপি টেবিলের উপরে এবং প্রতিটি কক্ষের ফলাফল অনুসারে অতিক্রম করি। সিকোয়েন্সটি গঠনের জন্য কোন ঘরটি বেছে নেওয়া হয়েছে তা আমরা স্থির করি।

কোড

সর্বাধিক দৈর্ঘ্যের স্নেক ক্রম সন্ধান করতে সি ++ কোড

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n=3, m=3;
  int grid[n][m] =
  {
    {1, 2, 3},
    {2, 4, 5},
    {1, 2, 1}
  };

  int dp[n][m];
  int mx = 0, en_i = -1, en_j = -1;
  for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j] = 1;
            if(i>0 && abs(grid[i-1][j]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i-1][j]+1, dp[i][j]);
            if(j>0 && abs(grid[i][j-1]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i][j-1]+1, dp[i][j]);
            if(dp[i][j] > mx){
                mx = dp[i][j];
                en_i = i;
                en_j = j;
            }
        }
  }
  cout<<"Maximum length of the Snake Sequence is: "<<mx<<endl;
  cout<<"The maximum length snake sequence is: ";
  int l_i = -1, l_j = -1;
  while(en_i != l_i || en_j != l_j){
        cout<<grid[en_i][en_j]<<" ";
        l_i = en_i, l_j = en_j;
        if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
            en_i--;
        else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
            en_j--;
  }
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

সর্বাধিক দৈর্ঘ্যের স্নেক ক্রম সন্ধান করতে জাভা কোড

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n=3, m=3;
    int grid[][] =
    {
      {1, 2, 3},
      {2, 4, 5},
      {1, 2, 1}
    };

    int dp[][] = new int[n][m];
    int mx = 0, en_i = -1, en_j = -1;
    for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
              dp[i][j] = 1;
              if(i>0 && Math.abs(grid[i-1][j]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j]);
              if(j>0 && Math.abs(grid[i][j-1]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i][j-1]+1, dp[i][j]);
              if(dp[i][j] > mx){
                  mx = dp[i][j];
                  en_i = i;
                  en_j = j;
              }
          }
    }
    System.out.println("Maximum length of the Snake Sequence is: "+mx);
    System.out.print("The maximum length snake sequence is: ");
    int l_i = -1, l_j = -1;
    while(en_i != l_i || en_j != l_j){
          System.out.print(grid[en_i][en_j]+" ");
          l_i = en_i; l_j = en_j;
          if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
              en_i--;
          else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
              en_j--;
    }
  	}
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এম), যেখানে এন এবং এম যথাক্রমে সারি এবং কলামের সংখ্যা। সময়ের জটিলতা গ্রিডের আকারের উপর নির্ভর করে। কারণ এটি গ্রিডে কক্ষের সংখ্যা গণনা করার জন্য প্রয়োজনীয়। সুতরাং সবচেয়ে খারাপ পরিস্থিতিতে আমাদের পুরো গ্রিডে ভ্রমণ করতে হবে।

স্পেস জটিলতা ity

ও (এন * এম), কারণ আমরা ইনপুট গ্রিডের মতো একই আকারের ডিপি গ্রিড তৈরি করি।