Унікальныя шляхі II


Узровень складанасці серада
Часта пытаюцца ў амазонка VMware
Дынамічнае праграмаванне матрыца

Дапусцім, мужчына стаіць у першай камеры ці ў левым верхнім куце "A × b" матрыца. Мужчына можа рухацца толькі ўверх альбо ўніз. Гэты чалавек хоча дабрацца да пункта прызначэння, і гэты пункт прызначэння для яго з'яўляецца апошняй ячэйкай матрыца альбо ніжні правы кут.

І калі ў гэтым ёсць некаторыя перашкоды, колькі унікальных шляхоў можа вызначыць чалавек. Дапамажыце яму дабрацца да пункта прызначэння, ведаючы "Унікальныя шляхі".

Перашкода ў матрыцы разглядаецца як 1, а прабел адзначаецца як 0.

Прыклад

Уваход:

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

Вынахад:

2

Тлумачэнне:

Паколькі ў сярэдзіне ўсёй матрыцы прысутнічае толькі адно перашкода, якое дазваляе толькі два унікальныя шляхі: -

  1. Уніз → Уніз → Управа → Управа
  2. Направа → направа → уніз → уніз

Унікальныя шляхі II

На малюнку вышэй сіняя стрэлка паказвае шлях 1, а чырвоная - шлях 2.

Алгарытм

  1. Праверце, ці змяшчае першая ячэйка, якая з'яўляецца масівам [0] [0], а потым вернеце унікальныя шляхі як 1, бо яна не можа рухацца наперад, чым гэта.
  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.

Такім чынам, набор, масіў [0] [0] = 1;

Ітэрацыя па калонцы,

я = 1

калі масіў [1] [0] == 0 і масіў [0] [0] = 1 дакладна

так масіў [1] [0] = 1;

i = 2;

калі масіў [2] [0] == 0 і масіў [1] [0] = 1 дакладна

так масіў [2] [0] = 1;

Зараз ітэрацыя па радку,

я = 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 - гэта наш неабходны выхад.

Рэалізацыя

Праграма C ++ для Unique Paths 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 для Unique Paths 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) бо лішняе месца не выкарыстоўваецца, бо мы выкарыстоўваем дынамічнае праграмаванне.

Спасылка