අද්විතීය මාර්ග 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 අඩංගු දැයි පරීක්ෂා කර බලා මෙයට වඩා ඉදිරියට යා නොහැකි බැවින් අද්විතීය මාර්ග 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 ].

උදාහරණයක්

එබැවින් අපි අරාව = {0,0,0}, {0,1,0}, {0,0,0 as as ලෙස උදාහරණයක් ගනිමු;

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 අපගේ අවශ්‍ය ප්‍රතිදානය බවයි.

ක්රියාත්මක කිරීම

අද්විතීය මාර්ග 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

අද්විතීය මාර්ග 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 යනු එක් එක් කොටුව සැකසෙන්නේ එක් වරක් පමණක් බැවින් අපට ලබා දී ඇති අනුකෘතියේ පේළි සහ තීරු ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අප භාවිතා කරන බැවින් අමතර ඉඩක් භාවිතා නොකරන බැවින් ගතික වැඩසටහන්කරණය.

විමර්ශන