Եզակի ուղիներ II


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon VMware
Դինամիկ ծրագրավորում Matrix

Ենթադրենք, մի մարդ կանգնած է առաջին խցում կամ վերին ձախ անկյունում «A × b» մատրիցա Տղամարդը կարող է շարժվել միայն կամ վեր կամ վար: Այդ մարդը ցանկանում է հասնել իր նպատակակետին, և այդ նպատակակետը նրա համար վերջին բջիջն է matrix կամ ներքևի աջ անկյունում:

Եվ եթե դրա մեջ կան որոշ խոչընդոտներ, ապա քանի յուրօրինակ ուղիներ կարող է անձը ճանաչել: Օգնեք նրան հասնել նպատակակետին ՝ իմանալով ոչ մի եզակի ուղի:

Խոչընդոտը մատրիցում համարվում է 1, իսկ տարածությունը նշվում է որպես 0:

Օրինակ

Մուտք:

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

Արդյունք:

2

Բացատրությունը.

Քանի որ ամբողջ մատրիցայի մեջտեղում կա միայն մեկ խոչընդոտ, որը թույլ է տալիս միայն երկու եզակի ուղիներ. -

  1. Down → Down → Right → Right
  2. Աջ → → → → → → → Down

Եզակի ուղիներ II

Վերոնշյալ պատկերում կապույտ սլաքը ցույց է տալիս ուղին 1, իսկ կարմիր սլաքը ցույց է տալիս ուղին 2:

Ալգորիթմ

  1. Ստուգեք, արդյոք [0] [0] զանգվածը պարունակող առաջին բջիջը պարունակում է 1, ապա վերադարձեք եզակի ուղիները որպես 0, քանի որ այն չի կարող առաջ շարժվել դրանից:
  2. Եթե ​​[0] [0] զանգվածը չի պարունակում 1 արժեք, ապա նախնականացրեք զանգվածի արժեքը [0] [0] = 1:
  3. Այժմ, կրկնեք զանգվածի առաջին շարքում և եթե այս բջիջը պարունակում է 1, սա նշանակում է, որ ներկայիս բջիջն իր մեջ խոչընդոտ ունի և բջիջի արժեքը դնում է 0: Այլապես այս բջիջի արժեքը սահմանեք նախորդ բջիջի համեմատ, array է [i] [j] = զանգված [i] [j-1]:
  4. Այժմ կրկնում ենք զանգվածի առաջին սյունակի վրա, և եթե այս բջիջը պարունակում է 1, սա նշանակում է, որ ներկայիս բջիջն իր մեջ խոչընդոտ ունի և վանդակի արժեքը դնում է 0: array է [i] [j] = զանգված [i] [j-1]:
  5. Այժմ, կրկնեք ամբողջ մատրիցով ՝ սկսած բջջային զանգվածից [1] [1]:
  6. Ստուգեք, եթե բջիջը որևէ խոչընդոտ չի պարունակում, ապա արա arrayi, j] = array [i-1, j] + array [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}};

Rayանգվածը փոխանցվում է 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;

i = 2;

եթե զանգվածը [2] [0] == 0 և զանգվածը [1] [0] = 1 ճիշտ է

այսպես զանգված [2] [0] = 1;

Այժմ կրկնվում է տողի վրայով,

i = 1

եթե զանգվածը [0] [1] == 0 և զանգվածը [0] [0] = 1 ճիշտ է

այսպես զանգված [0] [1] = 1;

i = 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-ը ճիշտ է

array [i] [j] = array [i - 1] [j] + array [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-ը ճիշտ է

array [i] [j] = array [i - 1] [j] + array [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

Java ծրագիր եզակի ուղիներ 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

Timeամանակի բարդություն

O (a × b) որտեղ a և b - տողերի և սյունների քանակն է մեզ տրված մատրիցում, քանի որ յուրաքանչյուր բջիջ մշակվում է միայն մեկ անգամ:

Տիեզերական բարդություն

Ո (1) քանի որ ոչ մի լրացուցիչ տարածք չի օգտագործվում, քանի որ մենք օգտագործում ենք դինամիկ ծրագրավորում.

Մանրամասն