ځانګړې لارې دوهم


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon VMware
متحرک برنامې جدول

فرض کړئ یو سړی په لومړي حجره یا د پورتنۍ کی corner اړخ کونج کې ولاړ دی "a × b" ميټرکس. یو انسان کولی شي یوازې پورته یا ښکته حرکت وکړي. دا شخص غواړي خپل منزل ته ورسي او دا د هغه لپاره منزل د حجرې وروستی حجره ده میټرکس يا ښي لاس کونج.

او که چیرې پدې کې یو څه خنډونه وي ، نو د سړي لخوا به څومره ځانګړې لارې وپیژندل شي. له هغه سره مرسته وکړئ چې د بې ساري لارو نه پیژندلو سره منزل ته ورسیږئ.

یو خنډ د 1 په توګه ګ .ل کیږي او ځای په میټریکس کې 0 په نښه شوی.

بېلګه

تفتیش:

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

محصول:

2

وضاحت:

ځکه چې د بشپړ میٹرکس په مینځ کې یوازې یو خنډ شتون لري کوم چې یوازې دوه ځانګړي لارې ته اجازه ورکوي: -

  1. لاندې → ښکته → ښي → ښي
  2. ښي - ښي - ښکته - ښکته

ځانګړې لارې دوهم

په پورتني عکس کې ، نیلي نیلي د 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 ارزښتونه ونه لري نو د دې معنی دا ده چې موږ د خپل منزل حجرې ته د رسېدو شمیرې لرو چې پورته خونې ته د رسېدو یو شمیر لارو مجموعه ده. حجره او د هغه حجرې کی left بائیں ته د لاسرسي د لارو شمیر.

نو موږ ځینې دندې پلي کړې چې زموږ سره زموږ د ستونزې په حل کې مرسته کوي. موږ د فنکشن ګیټ ویال اعلان کړ ، ګیټ وال ځینې دلیلونه ترلاسه کوي ځینې عملیات کوي او یو څه ارزښت بیرته ورکوي ، چې دا به لاندې ستونزه حل کړي:

  1. که په لومړي قطار کې ، یوه حجره یو ډول خنډ ولري دا 0 ته ارزښت ټاکي نو دا به د هغې حجرې ارزښت د تیر حجرې په څیر وټاکي چې سرنی دی [i] [j] = سرنی [i] [j-1 ].
  2. که په لومړي قطار کې ، یوه حجره یو ډول خنډ ولري دا 0 ته ارزښت ټاکي نو دا به د هغې حجرې ارزښت د تیر حجرې په څیر وټاکي چې سرنی دی [i] [j] = سرنی [i-1] [j ].

بېلګه

نو راځئ چې د تیر په څیر مثال واخلو = {{0,0,0،0,1,0،0,0,0} ، {XNUMX،XNUMX،XNUMX} ، {XNUMX،XNUMX،XNUMX}}؛

یو صف په موندیو یونیک پاټ کې تیریږي

صف = {{0,0,0،0,1,0،0,0,0} ، {XNUMX،XNUMX،XNUMX} ، {XNUMX،XNUMX،XNUMX}}؛

نو د هغې لومړۍ حجره چې صفونه ده [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 سم دی

سرنی [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 زموږ اړین محصول دی.

تطبیق

د ځانګړې لارې 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 د موږټکس کې د قطارونو او کالمونو شمیر دی چې موږ ته ورکړل شوی ځکه چې هر حجره یوازې یو ځل پروسس کیږي.

د ځای پیچلتیا

O (1) ځکه چې اضافي ځای نه کارول کیږي ځکه چې موږ کار کوو متحرک برنامه.

ماخذ