Јединствене стазе ИИ


Ниво тешкоће Средњи
Често питани у амазонка ВМваре
Динамичко програмирање матрица

Претпоставимо да човек стоји у првој ћелији или горњем левом углу „А × б“ матрица. Човек се може кретати само горе или доле. Та особа жели да стигне до свог одредишта и то одредиште за њу је последња ћелија матрица или доњи десни угао.

А ако постоје неке препреке, колико јединствених путева може да идентификује особа. Помозите му да стигне до одредишта знајући Не јединствених стаза.

Препрека се у матрици сматра 1, а размак је означен као 0.

Пример

Улаз:

[
[КСНУМКС],
[КСНУМКС],
[КСНУМКС]
]

Излаз:

2

objašnjenje:

Јер је усред целе матрице присутна само једна препрека која омогућава само две јединствене стазе: -

  1. Доље → Доље → Десно → Десно
  2. Десно → Десно → Доље → Доље

Јединствене стазе ИИ

На горњој слици плава стрелица показује путању 1, а црвена стрелицу 2.

Алгоритам

  1. Проверите да ли прва ћелија која је низ [0] [0] садржи 1, а затим вратите јединствене путање као 0 јер се не може померати напред од овога.
  2. Ако низ [0] [0] не садржи вредност 1, тада иницијализујте вредност низа [0] [0] = 1.
  3. Сада пређите преко првог реда низа и ако ова ћелија садржи 1, то значи да тренутна ћелија има препреку и поставља вредност ћелије на 0. Иначе подесите вредност ове ћелије у односу на претходну ћелију која је низ [и] [ј] = низ [и] [ј-1].
  4. Сада пређите преко прве колоне низа и ако ова ћелија садржи 1, то значи да тренутна ћелија има препреку и поставља вредност ћелије на 0. У супротном подесите вредност ове ћелије у односу на претходну ћелију која је низ [и] [ј] = низ [и] [ј-1].
  5. Сада извршите итерацију по целој матрици почев од поља ћелија [1] [1].
  6. Проверите да ли ћелија не садржи никакве препреке, онда направите арраии, ј] = арраи [и-1, ј] + арраи [и, ј-1].
  7. Ако ћелија садржи препреку, подесите вредност ћелије на 0 како бисте били сигурни да се неће поновити ни на једној другој путањи.

Објашњење

Дакле, наша главна идеја за решавање овог питања је ако ћелија у себи нема вредности 0, онда то значи да имамо број начина да дођемо до наше одредишне ћелије је збир бројних начина да дођемо до ћелије изнад тога ћелија и збир броја начина за постизање ћелије лево од те ћелије.

Тако смо имплементирали неке функције које ће нам помоћи у решавању нашег проблема. Прогласили смо функцију гетВал, гетВал добија неке аргументе, изводи неке операције и враћа неку вредност, што ће решити следећи проблем:

  1. Ако у првом реду ћелија садржи препреку, поставља вредност на 0, поставиће вредност те ћелије као вредност претходне ћелије која је низ [и] [ј] = низ [и] [ј-1 ].
  2. Ако у првом реду ћелија садржи препреку, поставља вредност на 0, поставиће вредност те ћелије као вредност претходне ћелије која је низ [и] [ј] = низ [и-1] [ј ].

Пример

Зато узмимо пример као Арраи = {{0,0,0}, {0,1,0}, {0,0,0}};

Низ се прослеђује у финдУникуеПатх

Низ = {{0,0,0}, {0,1,0}, {0,0,0}};

Дакле, његова прва ћелија која је низ [0] [0] није једнака 1.

Тако постављено, низ [0] [0] = 1;

Итерација преко колоне,

и = КСНУМКС

ако је низ [1] [0] == 0 и низ [0] [0] = 1 тачно

па низ [1] [0] = 1;

и = 2;

ако је низ [2] [0] == 0 и низ [1] [0] = 1 тачно

па низ [2] [0] = 1;

Сада понављање реда,

и = КСНУМКС

ако је низ [0] [1] == 0 и низ [0] [0] = 1 тачно

па низ [0] [1] = 1;

и = 2;

ако је низ [0] [2] == 0 и низ [0] [1] = 1 тачно

па низ [0] [2] = 1;

Сада полазимо од низа [1] [1]

и = 1, ј = 1

ако је низ [1] [1] == 0 нетачан

па низ [1] [1] = 0

и = 1, ј = 2

ако је низ [1] [2] == 0 тачно

низ [и] [ј] = низ [и - 1] [ј] + низ [и] [ј - 1];

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

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

и = 2, ј = 1

ако је низ [2] [1] == 0 тачно

па низ [2] [1] = 0

и = 2, ј = 2

ако је низ [2] [2] == 0 тачно

низ [и] [ј] = низ [и - 1] [ј] + низ [и] [ј - 1];

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

низ [2] [2] = 2 + 0;

низ [2] [2] = 2

То јест, вратићемо низ вредности [2] [2], што значи да је 2 наш потребан излаз.

Имплементација

Ц ++ програм за Уникуе Патхс ИИ

#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

Јава програм за Уникуе Патхс ИИ

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

Анализа сложености јединствених стаза ИИ

Сложеност времена

О (а × б) где су а и б број редова и колона у матрици која нам је дата пошто се свака ћелија обрађује само једном.

Сложеност простора

О (1) јер се не користи додатни простор од када ми користимо динамичко програмирање.

Препорука