ਵਿਲੱਖਣ ਮਾਰਗ II


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ VMware
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਮੈਟਰਿਕਸ

ਮੰਨ ਲਓ ਕਿ ਇੱਕ ਆਦਮੀ ਪਹਿਲੇ ਸੈੱਲ ਵਿੱਚ ਖੜ੍ਹਾ ਹੈ ਜਾਂ ਇਸਦੇ ਉਪਰਲੇ ਖੱਬੇ ਕੋਨੇ ਵਿੱਚ “ਏ × ਬੀ” ਮੈਟਰਿਕਸ. ਆਦਮੀ ਸਿਰਫ ਜਾਂ ਤਾਂ ਉੱਪਰ ਜਾਂ ਹੇਠਾਂ ਚਲ ਸਕਦਾ ਹੈ. ਉਹ ਵਿਅਕਤੀ ਆਪਣੀ ਮੰਜ਼ਿਲ 'ਤੇ ਪਹੁੰਚਣਾ ਚਾਹੁੰਦਾ ਹੈ ਅਤੇ ਉਸ ਲਈ ਮੰਜ਼ਿਲ ਉਸ ਦਾ ਆਖਰੀ ਸੈੱਲ ਹੈ ਮੈਟਰਿਕਸ ਜਾਂ ਹੇਠਾਂ ਸੱਜਾ ਕੋਨਾ.

ਅਤੇ ਜੇ ਇਸ ਵਿਚ ਕੁਝ ਰੁਕਾਵਟਾਂ ਹਨ, ਤਾਂ ਵਿਅਕਤੀ ਦੁਆਰਾ ਕਿੰਨੇ ਵਿਲੱਖਣ ਰਸਤੇ ਪਛਾਣੇ ਜਾ ਸਕਦੇ ਹਨ. ਵਿਲੱਖਣ ਮਾਰਗਾਂ ਦੀ ਕੋਈ ਨਹੀਂ ਜਾਣ ਕੇ ਮੰਜ਼ਿਲ ਤਕ ਪਹੁੰਚਣ ਵਿਚ ਉਸ ਦੀ ਸਹਾਇਤਾ ਕਰੋ.

ਇੱਕ ਰੁਕਾਵਟ ਨੂੰ 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] [ਜੇ -1].
  4. ਹੁਣ, ਐਰੇ ਦੇ ਪਹਿਲੇ ਕਾਲਮ ਉੱਤੇ ਦੁਹਰਾਓ ਅਤੇ ਜੇ ਇਸ ਸੈੱਲ ਵਿਚ 1 ਹੈ, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਮੌਜੂਦਾ ਸੈੱਲ ਵਿਚ ਇਕ ਰੁਕਾਵਟ ਹੈ ਅਤੇ ਸੈੱਲ ਦੀ ਕੀਮਤ 0 ਨਿਰਧਾਰਤ ਕਰਦੀ ਹੈ. ਨਹੀਂ ਤਾਂ ਪਿਛਲੇ ਸੈੱਲ ਦੀ ਤਰ੍ਹਾਂ ਇਸ ਸੈੱਲ ਦਾ ਮੁੱਲ ਨਿਰਧਾਰਤ ਕੀਤਾ ਗਿਆ ਹੈ. ਐਰੇ ਹੈ [i] [j] = ਐਰੇ [i] [ਜੇ -1].
  5. ਹੁਣ, ਸੈੱਲ ਐਰੇ [1] [1] ਤੋਂ ਸ਼ੁਰੂ ਹੋ ਰਹੇ ਪੂਰੇ ਮੈਟ੍ਰਿਕਸ ਤੇ ਦੁਹਰਾਓ.
  6. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਸੈੱਲ ਵਿੱਚ ਕੋਈ ਰੁਕਾਵਟ ਨਹੀਂ ਹੈ ਫਿਰ ਕਰੋ ਐਰੇ, ਜੇ] = ਐਰੇ [i-1, j] + ਐਰੇ [i, j-1].
  7. ਜੇ ਸੈੱਲ ਵਿਚ ਰੁਕਾਵਟ ਹੁੰਦੀ ਹੈ, ਤਾਂ ਸੈੱਲ ਦਾ ਮੁੱਲ 0 ਨਿਰਧਾਰਤ ਕਰੋ ਤਾਂ ਕਿ ਇਹ ਯਕੀਨੀ ਬਣਾਇਆ ਜਾ ਸਕੇ ਕਿ ਇਹ ਕਿਸੇ ਹੋਰ ਮਾਰਗ 'ਤੇ ਦੁਹਰਾ ਨਹੀਂ ਰਿਹਾ.

ਕਥਾ

ਇਸ ਲਈ ਇਸ ਪ੍ਰਸ਼ਨ ਨੂੰ ਸੁਲਝਾਉਣ ਲਈ ਸਾਡਾ ਮੁੱਖ ਵਿਚਾਰ ਇਹ ਹੈ ਕਿ ਜੇਕਰ ਸੈੱਲ ਦੇ ਅੰਦਰ 0 ਮੁੱਲ ਨਹੀਂ ਹਨ ਤਾਂ ਇਸਦਾ ਅਰਥ ਇਹ ਹੈ ਕਿ ਸਾਡੇ ਕੋਲ ਆਪਣੀ ਮੰਜ਼ਿਲ ਸੈੱਲ ਤੱਕ ਪਹੁੰਚਣ ਦੇ waysੰਗਾਂ ਦੀ ਸੰਖਿਆ ਹੈ ਉਸ ਉਪਰਲੇ ਸੈੱਲ ਤੱਕ ਪਹੁੰਚਣ ਦੇ ਕਈ ਤਰੀਕਿਆਂ ਦਾ ਜੋੜ. ਸੈੱਲ ਅਤੇ ਉਸ ਸੈੱਲ ਦੇ ਖੱਬੇ ਸੈੱਲ ਤੱਕ ਪਹੁੰਚਣ ਦੇ ਤਰੀਕਿਆਂ ਦੀ ਸੰਖਿਆ.

ਇਸ ਲਈ ਅਸੀਂ ਕੁਝ ਕਾਰਜਾਂ ਨੂੰ ਲਾਗੂ ਕੀਤਾ ਜੋ ਸਾਡੀ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਵਿੱਚ ਸਾਡੀ ਸਹਾਇਤਾ ਕਰਨ ਵਾਲੇ ਹਨ. ਅਸੀਂ ਫੰਕਸ਼ਨ getVal ਦਾ ਐਲਾਨ ਕੀਤਾ, getVal ਨੂੰ ਕੁਝ ਆਰਗੂਮਿੰਟ ਮਿਲਦੇ ਹਨ ਕੁਝ ਕਾਰਜ ਕਰਦੇ ਹਨ ਅਤੇ ਕੁਝ ਮੁੱਲ ਵਾਪਸ ਕਰਦੇ ਹਨ, ਜੋ ਕਿ ਹੇਠਲੀ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਜਾ ਰਿਹਾ ਹੈ:

  1. ਜੇ ਪਹਿਲੀ ਕਤਾਰ ਵਿਚ, ਇਕ ਸੈੱਲ ਇਕ ਰੁਕਾਵਟ ਰੱਖਦਾ ਹੈ, ਤਾਂ ਇਹ ਮੁੱਲ ਨੂੰ 0 ਦਰਸਾਉਂਦਾ ਹੈ ਨਹੀਂ ਤਾਂ ਇਹ ਉਸ ਸੈੱਲ ਦਾ ਮੁੱਲ ਸੈੱਲ ਦੇ ਪਿਛਲੇ ਸੈੱਲ ਦੀ ਤਰ੍ਹਾਂ ਸੈੱਟ ਕਰੇਗਾ [i] [ਜੇ] = ਐਰੇ [i] [ਜੇ -1 ].
  2. ਜੇ ਪਹਿਲੀ ਕਤਾਰ ਵਿਚ, ਇਕ ਸੈੱਲ ਇਕ ਰੁਕਾਵਟ ਰੱਖਦਾ ਹੈ, ਤਾਂ ਇਹ 0 ਨੂੰ ਮੁੱਲ ਨਿਰਧਾਰਤ ਕਰਦਾ ਹੈ ਨਹੀਂ ਤਾਂ ਇਹ ਉਸ ਸੈੱਲ ਦਾ ਮੁੱਲ ਸੈੱਲ ਦੇ ਪਿਛਲੇ ਸੈੱਲ ਦੀ ਤਰ੍ਹਾਂ ਸੈੱਟ ਕਰੇਗਾ [i] [ਜੇ] = ਐਰੇ [i-1] [j ].

ਉਦਾਹਰਨ

ਇਸ ਲਈ ਆਓ ਇੱਕ ਉਦਾਹਰਣ ਲੈੀਏ ਐਰੇ = {{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

ਜੇ ਐਰੇ [1] [0] == 0 ਅਤੇ ਐਰੇ [0] [0] = 1 ਸਹੀ ਹੈ

ਇਸ ਲਈ ਐਰੇ [1] [0] = 1;

i = 2;

ਜੇ ਐਰੇ [2] [0] == 0 ਅਤੇ ਐਰੇ [1] [0] = 1 ਸਹੀ ਹੈ

ਇਸ ਲਈ ਐਰੇ [2] [0] = 1;

ਹੁਣ ਕਤਾਰ ਵਿੱਚ ਦੁਹਰਾਓ,

ਮੈਂ = 1

ਜੇ ਐਰੇ [0] [1] == 0 ਅਤੇ ਐਰੇ [0] [0] = 1 ਸਹੀ ਹੈ

ਇਸ ਲਈ ਐਰੇ [0] [1] = 1;

i = 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 ਸਹੀ ਹੈ

ਐਰੇ [i] [ਜੇ] = ਐਰੇ [i - 1] [ਜੇ] + ਐਰੇ [i] [ਜੇ - 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 ਸਹੀ ਹੈ

ਐਰੇ [i] [ਜੇ] = ਐਰੇ [i - 1] [ਜੇ] + ਐਰੇ [i] [ਜੇ - 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

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਏ × ਬੀ) ਜਿੱਥੇ a ਅਤੇ b ਸਾਨੂੰ ਦਿੱਤੇ ਗਏ ਮੈਟ੍ਰਿਕਸ ਵਿੱਚ ਕਤਾਰਾਂ ਅਤੇ ਕਾਲਮਾਂ ਦੀ ਸੰਖਿਆ ਹੈ ਕਿਉਂਕਿ ਹਰ ਸੈੱਲ ਸਿਰਫ ਇਕ ਵਾਰ ਪ੍ਰਕਿਰਿਆ ਕੀਤੀ ਜਾਂਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1) ਕਿਉਂਕਿ ਕੋਈ ਅਤਿਰਿਕਤ ਥਾਂ ਦੀ ਵਰਤੋਂ ਨਹੀਂ ਕੀਤੀ ਜਾ ਰਹੀ ਕਿਉਂਕਿ ਅਸੀਂ ਵਰਤ ਰਹੇ ਹਾਂ ਗਤੀਸ਼ੀਲ ਪ੍ਰੋਗਰਾਮਿੰਗ.

ਹਵਾਲਾ