יינציק פּאַטס וו  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן וומוואַרע
דינאַמיש פּראָגראַממינג מאַטריץ

רעכן אַ מענטש שטייענדיק אין דער ערשטער צעל אָדער די שפּיץ לינקס ווינקל פון “אַ × ב” מאַטריץ. א מענטש קען מאַך נאָר אַרויף אָדער אַראָפּ. דער מענטש וויל דערגרייכן זיין דעסטיניישאַן און דער דעסטיניישאַן פֿאַר אים איז די לעצטע צעל פון די מאַטריץ אָדער רעכט רעכט ווינקל.

און אויב עס זענען עטלעכע כערדאַלז, ווי פילע יינציק פּאַטס קענען זיין יידענאַפייד דורך דעם מענטש. הילף אים צו דערגרייכן דעם דעסטיניישאַן דורך וויסן ניט קיין יינציק פּאַטס.

א שטערונג איז גערעכנט ווי 1 און פּלאַץ איז אנגעצייכנט ווי 0 אין די מאַטריץ.

בייַשפּיל  

ינפּוט:

[
[0,0,0],
[0,1,0],
[קסנומקס]
]

אָוטפּוט:

2

דערקלערונג:

ווייַל בלויז איין שטערונג איז פאָרשטעלן אין די מיטל פון די גאנצע מאַטריץ, וואָס אַלאַוז בלויז צוויי יינציק פּאַטס: -

  1. אַראָפּ → אַראָפּ → רעכט → רעכט
  2. רעכט → רעכט → אַראָפּ → אַראָפּ

יינציק פּאַטס וושפּילקע

אין די אויבן בילד, די בלוי פייַל ווייזט דרך 1 און די רויט פייַל ווייזט דרך 2.

אַלגאָריטהם  

  1. קוק אויב דער ערשטער צעל וואָס איז מענגע [0] [0] כּולל 1, דאַן די יינציק פּאַטס ווי 0 ווייַל עס קען נישט פאָרויס ווי דאָס.
  2. אויב מענגע [0] [0] כּולל נישט די ווערט 1 יניטיאַליזירן די ווערט פון מענגע [0] [0] = 1.
  3. איצט, יטעראַטע איבער דער ערשטער רודערן פון די מענגע, און אויב דער צעל כּולל 1, דאָס מיינט אַז די קראַנט צעל האט אַ שטערונג און באַשטעטיקט די ווערט פון אַ צעל צו 0. אַנדערש שטעלן די ווערט פון דעם צעל ווי די פֿריִערדיקע צעל וואָס איז מענגע [איך] [דזש] = מענגע [איך] [דזש -1].
  4. איצט, יטערייט איבער דער ערשטער זייַל פון דער מענגע, און אויב דער צעל כּולל 1, דאָס מיינט אַז די קראַנט צעל האט אַ שטערונג און באַשטעטיקט די ווערט פון די צעל צו 0. אַנדערש שטעלן די ווערט פון דעם צעל ווי די פריערדיקע צעל וואָס איז מענגע [איך] [דזש] = מענגע [איך] [דזש -1].
  5. איצט יטעראַטע איבער די גאנצע מאַטריץ סטאַרטינג פון די סעלל מענגע [1] [1].
  6. קוק אויב צעל כּולל קיין שטערונג, טאָן אַרטיי, דזש] = מענגע [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] [0] == 0 און מענגע [0] [0] = 1 איז אמת

אַזוי מענגע [1] [0] = 1;

איך = 2;

אויב מענגע [2] [0] == 0 און מענגע [1] [0] = 1 איז אמת

אַזוי מענגע [2] [0] = 1;

איצט יטערייטינג איבער רודערן,

איך = קסנומקס

אויב מענגע [0] [1] == 0 און מענגע [0] [0] = 1 איז אמת

אַזוי מענגע [0] [1] = 1;

איך = 2;

אויב מענגע [0] [2] == 0 און מענגע [0] [1] = 1 איז אמת

אַזוי מענגע [0] [2] = 1;

איצט סטאַרטינג פון מענגע [1] [1]

איך = 1, דזש = 1

אויב מענגע [1] [1] == 0 איז פאַלש

אַזוי מענגע [1] [1] = 0

איך = 1, דזש = 2

אויב מענגע [1] [2] == 0 איז אמת

זע אויך
K-th סמאָלאַסט עלעמענט אין אַ סאָרטעד מאַטריץ

מענגע [איך] [דזש] = מענגע [איך - 1] [דזש] + מענגע [איך] [דזש - 1];

so array[1][2]=array[0][2]+array[0][1];

array[1][2]=1+1=2;

איך = 2, דזש = 1

אויב מענגע [2] [1] == 0 איז אמת

אַזוי מענגע [2] [1] = 0

איך = 2, דזש = 2

אויב מענגע [2] [2] == 0 איז אמת

מענגע [איך] [דזש] = מענגע [איך - 1] [דזש] + מענגע [איך] [דזש - 1];

so array[2][2]=array[1][2]+array[2][1];

מענגע [2] [2] = 2 + 0;

מענגע [2] [2] = 2

מיר וועלן צוריקקומען די ווערט מענגע [2] [2] וואָס מיטל 2 איז אונדזער פארלאנגט רעזולטאַט.

ימפּלעמענטאַטיאָן  

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

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר יינציק פּאַטס וו  

צייט קאַמפּלעקסיטי

אָ (אַ × ב) וווּ a און b איז די נומער פון ראָוז און שפאלטן אין די מאַטריץ וואָס איז געגעבן צו אונדז ווייַל יעדער צעל איז פּראַסעסט בלויז אַמאָל.

זע אויך
דרוק אַלע דיסטריביאַטאַד עלעמענטן פון אַ געגעבן ינטעגער עריי

ספעיס קאַמפּלעקסיטי

אָ (1) ווי קיין עקסטרע פּלאַץ איז יוטאַלייזד זינט מיר נוצן דינאַמיש פּראָגראַממינג.

דערמאָנען