იპოვნეთ გველის მაქსიმალური სიგრძე


Რთული ტური Hard
ხშირად ეკითხებიან Amazon CodeNation Expedia Yandex
დინამიური პროგრამირება Matrix

პრობლემა "იპოვნეთ მაქსიმალური სიგრძის გველის მიმდევრობა" აცხადებს, რომ ჩვენ გვეძლევა ა ქსელის შეიცავს რიცხვები. ამოცანაა გველის თანმიმდევრობის მოძებნა მაქსიმალური სიგრძით. თანმიმდევრობა, რომელსაც აქვს მიმდებარე რიცხვები ქსელში, აბსოლუტური სხვაობით 1, ცნობილია როგორც Snake თანმიმდევრობა. ნომრის მიმდებარე ელემენტებია ის რიცხვები, რომლებიც ის დარჩა და მეზობლების ზემოთ, იმის გათვალისწინებით, რომ ისინი ქსელის შიგნით არსებობს. ფორმალურად რომ ვთქვათ, თუ თქვენ დგახართ ქსელის (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

განმარტება

იპოვნეთ გველის მაქსიმალური სიგრძე

მიდგომა

პრობლემა ითხოვს გველის თანმიმდევრობის მაქსიმალურ სიგრძეს და ჩვენ შემოგვთავაზებენ ქსელს. გულუბრყვილო ან უხეში ძალის მიდგომა უნდა დაიწყოს ქსელის ზედა მარცხენა კუთხიდან და რეკურსის გამოყენება გადის მის მარჯვენა და ქვედა მეზობელში. ანალოგიურად ამ უჯრედებიდან მიდიან მეზობლებთან და ასე შემდეგ, სანამ არ იპოვნებთ უჯრედს ისეთი, რომ წინსვლა არ არის დაწესებული პირობების გამო. რეკურსიის გამოყენება, სადაც ზოგადად გვაქვს ოთხი რეკურსიული ზარი, დროის სირთულე უფრო მაღალ მხარეზე იქნება.

ზემოთ მოცემული მიდგომის ნაცვლად, ჩვენ შეგვიძლია წავიდეთ დინამიური პროგრამირება რადგან ჩვენ აღწერს პრობლემას რეკურსიული ამოხსნის გამოყენებით. შემდეგ უბრალოდ გაიხსენეთ იგი, რომ გამოსავალი მიიღოთ. დროის სირთულე ზემოთ მოყვანილი მიდგომისთვის ექსპონენციალური იყო, მაგრამ გამოიყენა დინამიური პროგრამირება შეუძლია შეამციროს იგი მრავალწევრამდე. ამ პრობლემისთვის, ჩვენ შევხედავთ ორ მდგომარეობას, პირველ რიგში, მწკრივის ინდექსი და შემდეგ სვეტის ინდექსი. თითოეული უჯრედი DP ცხრილში იქნება დამოკიდებული მის ზემოთ და მხოლოდ მარცხენა უჯრედზე. თუ ჩვენ გვჭირდება საკნები, რომლებიც არჩეულია პასუხისთვის, ჩვენ გადავკვეთთ DP ცხრილს და თითოეული უჯრედის შედეგის მიხედვით. ჩვენ წყვეტთ რომელი უჯრედი აიყვანეს თანმიმდევრობის შესაქმნელად.

კოდი

C ++ კოდი მაქსიმალური სიგრძის გველის მიმდევრობის მოსაძებნად

#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

სირთულის ანალიზი

დროის სირთულე

O (N * M), სადაც N და M შესაბამისად არის სტრიქონების და სვეტების რაოდენობა. დროის სირთულე დამოკიდებულია ქსელის ზომაზე. რადგან ეს საჭიროა ქსელში უჯრედების რაოდენობის გამოსათვლელად. ამრიგად, ყველაზე ცუდ შემთხვევაში, ჩვენგან მთელი ქსელის გავლა მოეთხოვებათ.

სივრცის სირთულე

O (N * M), რადგან ჩვენ ვქმნით იმავე ზომის DP ქსელს, როგორც შეყვანის ქსელს.