അദ്വിതീയ പാതകൾ II


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ വിഎംവെയർ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മാട്രിക്സ്

ആദ്യത്തെ സെല്ലിലോ മുകളിൽ ഇടത് മൂലയിലോ ഒരാൾ നിൽക്കുന്നുവെന്ന് കരുതുക “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;

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 ശരിയാണെങ്കിൽ

അറേ [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 നായുള്ള സി ++ പ്രോഗ്രാം

#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) ഞങ്ങൾ ഉപയോഗിക്കുന്നതിനാൽ അധിക സ്ഥലമൊന്നും ഉപയോഗിക്കാത്തതിനാൽ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്.

അവലംബം