अद्वितीय पथहरू दोस्रो  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन VMware
डायनामिक प्रोग्रामिंग म्याट्रिक्स

मानौं एउटा मान्छे पहिलो सेलमा उभिरहेको छ वा माथि बायाँ कुनामा "A × b" म्याट्रिक्स एउटा मानिस मात्र माथि वा तल सार्न सक्छ। त्यो व्यक्ति आफ्नो गन्तव्यमा पुग्न चाहन्छ र उसको लागि त्यो गन्तव्य उसको अन्तिम कक्ष हो म्याट्रिक्स वा तल दायाँ कुना।

र यदि यसमा केहि अवरोधहरू छन् भने, व्यक्ति द्वारा कति अनौंठो पथहरू चिन्न सकिन्छ। उसलाई गन्तव्यमा पुग्न मद्दत गर्नुहोस् अनौंठो पथहरूको कुनै छैन भनेर।

अवरोध १ को रूपमा मानिन्छ र ठाउँलाई म्याट्रिक्समा ० को रूपमा चिन्ह लगाइएको छ।

उदाहरणका  

इनपुट:

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

उत्पादन:

2

व्याख्या:

किनकि केवल एउटा बाधा सम्पूर्ण म्याट्रिक्सको बिचमा अवस्थित छ जसले केवल दुई अद्वितीय मार्गहरूलाई अनुमति दिन्छ:

  1. तल → डाउन → दायाँ → दाँया
  2. दायाँ → दाँया → डाउन → डाउन

अद्वितीय पथहरू दोस्रोपिन

माथिको छविमा, निलो एरोले मार्ग १ देखाउँदछ र रातो एर्रोले मार्ग २ देखाउँदछ।

अल्गोरिदम  

  1. पहिलो सेल जुन एर्रे छ [०] [०] मा १ समावेश छ भने अद्वितीय पथ ० लाई फर्काउनुहोस् किनकि यो भन्दा अगाडि बढ्न सक्दैन।
  2. यदि एर्रे [०] [०] ले मान १ समावेश गर्दैन भने एर्रेको मान आरम्भ गर्नुहोस् [०] [०] = १।
  3. अब, एर्रेको पहिलो प row्क्तिमा पुनरावृत्ति गर्नुहोस् र यदि यो सेल १ समावेश गर्दछ, यसको मतलब हालको सेलले यसमा अवरोध राख्छ र सेलको मान ० मा सेट गर्दछ। अन्यथा अघिल्लो सेलको रूपमा यस सेलको मान सेट गर्दछ जुन एर्रे हो [i] [j] = एर्रे [i] [j-1]।
  4. अब एरेको पहिलो स्तम्भमा पुनरावृत्ति गर्नुहोस् र यदि यो सेल १ समावेश गर्दछ, यसको मतलब हालको सेलले यसमा अवरोध राख्छ र सेलको मान ० मा सेट गर्दछ। अन्यथा यो सेलको मान अघिल्लो सेलको रूपमा सेट गर्दछ जुन एर्रे हो [i] [j] = एर्रे [i] [j-1]।
  5. अब, सेल एर्रे [१] [१] बाट सुरू गरेर सम्पूर्ण म्याट्रिक्समा पुनरावृत्ति गर्नुहोस्।
  6. यदि सेलले कुनै बाधा समावेश गर्दैन भने जाँच गर्नुहोस् तब एर्रे, जे] = एर्रे [i-1, j] + एर्रे [i, j-1] गर्नुहोस्।
  7. यदि सेलमा बाधा समावेश छ भने, त्यसपछि सेलको मान ० मा सेट गर्नुहोस् यो निश्चित गर्न को लागी कि यसले अन्य कुनै पनि मार्गमा दोहोर्याउँदैन।
पनि हेर्नुहोस्
स्ट्रि Le लेटकोड समाधानको रिभर्स स्वरहरू

स्पष्टीकरण  

त्यसोभए यस प्रश्नको समाधानका लागि हाम्रो मुख्य विचार भनेको यदि सेलमा यसका मानहरू ० छैनन् भने यसको अर्थ यो छ कि हामीसँग हाम्रो गन्तव्य सेलमा पुग्ने तरिकाहरू धेरै छन् त्यस माथिको सेलमा पुग्ने धेरै तरिकाहरूका योगहरू। सेल र त्यो सेलको बाँया सेलमा पुग्ने तरिकाहरूको संख्याको योग।

त्यसैले हामीले केहि कार्यहरू कार्यान्वयन गर्यौं जसले हामीलाई हाम्रो समस्या समाधान गर्न मद्दत गर्नेछ। हामीले एउटा समारोह getVal घोषित गर्‍यौं, getVal ले केही आर्गुमेन्टहरू पाउँदछ र केही मान दिन्छ, जुन निम्न समस्यालाई सुल्झाउने छ।

  1. यदि पहिलो प row्क्तिमा, सेलले अवरोध समावेश गर्दछ यसले ० लाई मान सेट गर्दछ अन्यथा त्यो सेलको मान सेट गर्दछ अघिल्लो सेलको सरर [i] [j] = एरे [i] [j-0 ]।
  2. यदि पहिलो प row्क्तिमा, सेलले एउटा अवरोध समावेश गर्दछ यसले ० लाई मान सेट गर्दछ अन्यथा त्यो सेलको मान सेट गर्दछ अघिल्लो सेलको सरर [i] [j] = एरे [i-0] [j ]।

उदाहरणका

त्यसो भए हामी एर्रे = {, ०,०,०}, {०,१,०}, {०,०,०}} को रूपमा उदाहरण लिन सक्छौं;

एउटा एर्रे FindUniquePath मा पास गरियो

एर्रे = {{०,०,०}, {०,१,०}, {०,०,०}};

त्यसैले यसको पहिलो सेल जुन एर्रे [०] [०] १ बराबर छैन।

त्यसैले सेट, एर्रे [०] [०] [१]

स्तम्भमा इटरेटिंग,

i = ०

यदि एर्रे [१] [०] == ० र एर्रे [०] [०] = १ सही छ

त्यसैले एर्रे [१] [०] = १;

i = 2;

यदि एर्रे [१] [०] == ० र एर्रे [०] [०] = १ सही छ

त्यसैले एर्रे [१] [०] = १;

अब प row्क्ति माथि पुनरावृत्ति,

i = ०

यदि एर्रे [१] [०] == ० र एर्रे [०] [०] = १ सही छ

त्यसैले एर्रे [१] [०] = १;

i = 2;

यदि एर्रे [१] [०] == ० र एर्रे [०] [०] = १ सही छ

त्यसैले एर्रे [१] [०] = १;

अब एर्रेबाट सुरू गर्दै [१] [१]

i = 1, j = 1

यदि एर्रे [१] [१] == ० गलत छ

त्यसैले एर्रे [१] [१] = ०

i = 1, j = 2

यदि एर्रे [१] [२] == ० सही छ

पनि हेर्नुहोस्
क्रमबद्ध गरिएको म्याट्रिक्समा K-th सबैभन्दा सानो एलिमेन्ट

एर्रे [i] [j] = एर्रे [i - १] [j] + एर्रे [i] [j - १];

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

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

i = 2, j = 1

यदि एर्रे [१] [२] == ० सही छ

त्यसैले एर्रे [१] [१] = ०

i = 2, j = 2

यदि एर्रे [१] [२] == ० सही छ

एर्रे [i] [j] = एर्रे [i - १] [j] + एर्रे [i] [j - १];

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

एर्रे [२] [२] = २ + ०;

एर्रे [२] [२] = २

त्यो हो हामी मान एरे [२] [२] फर्काउने छौं जसको अर्थ २ हाम्रो आवाश्यक आउटपुट हो।

कार्यान्वयन  

C ++ अद्वितीय पथहरू 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

अद्वितीय पथ २ को लागी जाभा प्रोग्राम

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

अद्वितीय पथहरू २ को लागि जटिलता विश्लेषण  

समय जटिलता

O (a × b) जहाँ a र b पows्क्ति र स्तम्भहरूको संख्या हो जुन हामीलाई दिइएको म्याट्रिक्समा प्रत्येक सेलको रूपमा एकचोटि प्रशोधन गरिन्छ।

पनि हेर्नुहोस्
दिइएको पूर्णांक एरेको सबै भिन्न तत्वहरू प्रिन्ट गर्नुहोस्

ठाउँ जटिलता

O (१) कुनै अतिरिक्त ठाउँ प्रयोग भएको छैन किनकी हामी प्रयोग गर्दैछौं गतिशील प्रोग्रामिंग.

संदर्भ