Unique Paths II


Кыйынчылык деңгээли орто
Көп суралган Amazon VMware
Динамикалык программалоо Matrix

Биринчи камерада же сол жактын жогорку сол бурчунда турган адам дейли “A × b” матрица. Эркек өйдө же ылдый гана кыймылдай алат. Ал адам көздөгөн жерине жетүүнү каалайт жана ал көздөгөн жердин акыркы уячасы Булакта же төмөнкү оң бурч.

Эгер анда кандайдыр бир тоскоолдуктар болсо, адам тарабынан канча уникалдуу жолду аныктоого болот. Ага Уникалдуу Жолдорду билбей, көздөгөн жерине жетүүгө жардам бериңиз.

Тоскоолдук 1 деп эсептелет, ал эми матрицада орун 0 деп белгиленет.

мисал

киргизүү:

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

Output:

2

Explanation:

Себеби бүтүндөй матрицанын ортосунда бир гана тоскоолдук бар, бул эки гана уникалдуу жолго мүмкүндүк берет: -

  1. Төмөн → Төмөн → Оң → Оң
  2. Оң → Оң → Төмөн → Төмөн

Unique Paths II

Жогорудагы сүрөттө көк жебе 1-жолду жана кызыл жебе 2-жолду көрсөтөт.

Algorithm

  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. Уячанын тоскоолдук жок экендигин текшериңиз, анда 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}} мисалын алалы;

Массив findUniquePath өткөрүлүп берилет

Массив = {{0,0,0}, {0,1,0}, {0,0,0}};

Ошентип, анын [0] [0] массивинин биринчи уячасы 1ге барабар эмес.

So set, array [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 чын болсо

массив [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 биздин талап кылган натыйжабыз.

ишке ашыруу

Unique Paths II үчүн C ++ программасы

#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

Unique Paths II үчүн Java программасы

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) мында а жана b - ар бир уяча бир эле жолу иштетилгендиктен, бизге берилген матрицанын катарлары менен тилкелеринин саны.

Космостун татаалдыгы

O (1) анткени биз пайдаланып жаткандыктан, ашыкча орун колдонулбай жатат динамикалык программалоо.

шилтеме