უნიკალური ბილიკები II


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon VMware
დინამიური პროგრამირება Matrix

დავუშვათ, კაცი დგას პირველ საკანში ან ზედა მარცხენა კუთხეში "A × b" მატრიცა კაცს შეუძლია მოძრაობა მხოლოდ ზევით ან ქვევით. ამ ადამიანს სურს მიაღწიოს დანიშნულების ადგილს და ეს დანიშნულება მისთვის ბოლო უჯრედია matrix ან ქვედა მარჯვენა კუთხე.

და თუ მასში რაიმე დაბრკოლებაა, რამდენი უნიკალური ბილიკის დადგენა შეუძლია ადამიანს. დაეხმარეთ მას დანიშნულების ადგილამდე მისასვლელად, იცოდეს No უნიკალური ბილიკები.

დაბრკოლება ითვლება 1-ით, ხოლო სივრცე აღინიშნება 0-ით მატრიცაში.

მაგალითი

შეყვანის:

[
[0,0,0],
[0,1,0],
[0,0,0]
]

გამოყვანის:

2

განმარტება:

რადგან მთელი მატრიცის შუაში მხოლოდ ერთი დაბრკოლებაა, რაც მხოლოდ ორ უნიკალურ გზას იძლევა: -

  1. ქვემოთ → ქვემოთ → მარჯვნივ → მარჯვნივ
  2. მარჯვნივ → მარჯვნივ → ქვემოთ → ქვემოთ

უნიკალური ბილიკები II

ზემოთ გამოსახულებაში ლურჯი ისარი აჩვენებს ბილიკს 1, ხოლო წითელ ისარს ბილიკი 2.

ალგორითმი

  1. შეამოწმეთ არის თუ არა პირველი უჯრედი, რომელიც არის მასივი [0] [0], შეიცავს 1-ს, შემდეგ დააბრუნეთ უნიკალური ბილიკები 0-ით, რადგან მასზე წინსვლა არ შეუძლია.
  2. თუ მასივი [0] [0] არ შეიცავს 1 მნიშვნელობას, მას შემდეგ უნდა ჩამოვაყალიბოთ მასივი [0] [0] = 1.
  3. ახლა, გამეორება მასივის პირველ რიგზე და თუ ეს უჯრედი შეიცავს 1-ს, ეს ნიშნავს, რომ ამჟამინდელ უჯრედს აქვს დაბრკოლება და უჯრედის მნიშვნელობას ადგენს 0-ზე. სხვას ამ უჯრედის მნიშვნელობა მიუთითეთ წინა უჯრისთვის, არის მასივი [i] [j] = მასივი [i] [j-1].
  4. ახლა, გამეორება მასივის პირველ სვეტზე და თუ ეს უჯრედი შეიცავს 1-ს, ეს ნიშნავს, რომ ამჟამინდელ უჯრედს აქვს დაბრკოლება და უჯრედის მნიშვნელობას ადგენს 0. სხვა. ამ უჯრედის მნიშვნელობა დააყენეთ წინა უჯრისთვის, არის მასივი [i] [j] = მასივი [i] [j-1].
  5. ახლა, გამეორება მთელ მატრიცაზე, დაწყებული უჯრედის მასივიდან [1] [1].
  6. შეამოწმეთ, თუ უჯრედი არ შეიცავს რაიმე დაბრკოლებას, გააკეთეთ მასივი, j] = მასივი [i-1, j] + მასივი [i, j-1].
  7. თუ უჯრედი შეიცავს დაბრკოლებას, მაშინ დააყენეთ უჯრედის მნიშვნელობა 0-ზე, რათა დარწმუნდეთ, რომ იგი არ მეორდება სხვა გზაზე.

განმარტება

ამ საკითხის გადაჭრის ჩვენი მთავარი იდეაა: თუ უჯრედს არ აქვს 0 მნიშვნელობები, ეს ნიშნავს, რომ ჩვენ გვაქვს დანიშნულების უჯრედის მიღწევის გზების რაოდენობა, არის უჯრედის მიღწევის მრავალი გზა უჯრედი და ამ უჯრედის დარჩენილი უჯრედის მიღწევის გზების რაოდენობის ჯამი.

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

  1. თუ პირველ რიგში, უჯრედი შეიცავს დაბრკოლებას, იგი ადგენს მნიშვნელობას 0 სხვაზე, ის ადგენს ამ უჯრედის მნიშვნელობას, როგორც წინა უჯრედს, რომელიც არის მასივი [i] [j] = მასივი [i] [j-1 ].
  2. თუ პირველ რიგში, უჯრედი შეიცავს დაბრკოლებას, იგი ადგენს მნიშვნელობას 0 სხვაზე, ის ადგენს ამ უჯრედის მნიშვნელობას, როგორც წინა უჯრედს, რომელიც არის მასივი [i] [j] = მასივი [i-1] [j ].

მაგალითი

მოდით ავიღოთ მაგალითი, როგორც Array = {{0,0,0}, {0,1,0}, {0,0,0}};

მასივი გადადის findUniquePath- ში

მასივი = {{0,0,0}, {0,1,0}, {0,0,0}};

ასე რომ, მისი პირველი უჯრედი, რომელიც არის მასივი [0] [0], არ არის 1-ის ტოლი.

ასე დააყენეთ, მასივი [0] [0] = 1;

განმეორება სვეტზე,

i = 1

თუ მასივი [1] [0] == 0 და მასივი [0] [0] = 1 არის მართალი

ასე რომ მასივი [1] [0] = 1;

მე = 2;

თუ მასივი [2] [0] == 0 და მასივი [1] [0] = 1 არის მართალი

ასე რომ მასივი [2] [0] = 1;

ახლა მეორდება რიგის ზევით,

i = 1

თუ მასივი [0] [1] == 0 და მასივი [0] [0] = 1 არის მართალი

ასე რომ მასივი [0] [1] = 1;

მე = 2;

თუ მასივი [0] [2] == 0 და მასივი [0] [1] = 1 არის მართალი

ასე რომ მასივი [0] [2] = 1;

ახლა იწყება მასივიდან [1] [1]

i = 1, j = 1

თუ მასივი [1] [1] == 0 არასწორია

ასე რომ მასივი [1] [1] = 0

i = 1, j = 2

თუ მასივი [1] [2] == 0 არის მართალი

მასივი [i] [j] = მასივი [i - 1] [j] + მასივი [i] [j - 1];

so array[1][2]=array[0][2]+array[0][1];

array[1][2]=1+1=2;

i = 2, j = 1

თუ მასივი [2] [1] == 0 არის მართალი

ასე რომ მასივი [2] [1] = 0

i = 2, j = 2

თუ მასივი [2] [2] == 0 არის მართალი

მასივი [i] [j] = მასივი [i - 1] [j] + მასივი [i] [j - 1];

so array[2][2]=array[1][2]+array[2][1];

მასივი [2] [2] = 2 + 0;

მასივი [2] [2] = 2

ეს არის ის, რომ ჩვენ ვაპირებთ დავაბრუნოთ მნიშვნელობის მასივი [2] [2], რაც ნიშნავს, რომ 2 არის ჩვენი საჭირო გამომავალი.

განხორციელება

C ++ პროგრამა უნიკალური გზებისთვის II

#include<iostream>
using namespace std;
int getVal(int x, int y)
{
    if(x==0 && y==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int findUniquePath(int arr[3][3])
{
    if (arr[0][0] == 1)
    {
        return 0;
    }
    arr[0][0] = 1;
    for (int i = 1; i < 3; i++)
    {
        arr[i][0] = getVal(arr[i][0],arr[i-1][0]);
    }
    for (int i = 1; i < 3; i++)
    {
        arr[0][i] = getVal(arr[0][i],arr[0][i-1]);
    }
    for (int i = 1; i < 3; i++)
    {
        for (int j = 1; j < 3; j++)
        {
            if (arr[i][j] == 0)
            {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
            else
            {
                arr[i][j] = 0;
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputValue[3][3]= {{0,0,0},
                           {0,1,0},
                           {0,0,0}};
                           
    findUniquePath(inputValue);
    cout<<findUniquePath(inputValue);;
    return 0;
}
2

ჯავა პროგრამა უნიკალური ბილიკებისთვის II

class uniquePath2 {
  public static int getVal(int x, int y) {
    if (x == 0 && y == 1) {
      return 1;
    } else {
      return 0;
    }
  }
  public static int findUniquePath(int array[][]) {
    if (array[0][0] == 1) {
      return 0;
    }
    array[0][0] = 1;
    for (int i = 1; i<array.length; i++) {
      array[i][0] = getVal(array[i][0], array[i - 1][0]);
    }
    for (int i = 1; i<array[0].length; i++) {
      array[0][i] = getVal(array[0][i], array[0][i - 1]);
    }
    for (int i = 1; i<array.length; i++) {
      for (int j = 1; j<array[i].length; j++) {
        if (array[i][j] == 0) {
          array[i][j] = array[i - 1][j] + array[i][j - 1];
        } else {
          array[i][j] = 0;
        }
      }
    }

    int row = array.length;
    int col = array[0].length;
    return array[row - 1][col - 1];
  }
  public static void main(String[] args) {
    int inputValue[][] = {
      {
        0, 0, 0
      }, {
        0, 1, 0
      }, {
        0, 0, 0
      }
    };
    System.out.println(findUniquePath(inputValue));
  }
}
2

სირთულის ანალიზი უნიკალური ბილიკებისთვის II

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

O (a × b) სადაც a და b არის რიგების და სვეტების რაოდენობა მატრიცაში, რომელიც მოცემულია ჩვენთვის, რადგან თითოეული უჯრედი მხოლოდ ერთხელ მუშავდება.

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

O (1) რადგან დამატებითი ადგილი არ გამოიყენება, რადგან ჩვენ ვიყენებთ დინამიური პროგრამირება.

Reference