Рубрики

Подсчитайте количество путей с не более чем k поворотами

Учитывая матрицу «mxn», подсчитайте количество путей, чтобы достичь нижнего правого от верхнего левого угла с максимально допустимым k витков.

Какой поворот? Движение считается поворотом, если мы двигались вдоль ряда и теперь двигались вдоль колонны. ИЛИ мы двигались вдоль колонны и теперь движемся вдоль ряда.

There are two possible scenarios when a turn can occur
at point (i, j):

Turns Right: (i-1, j)  ->  (i, j)  ->  (i, j+1)
                      Down        Right

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)
                     Right        Down

Примеры:

Input:  m = 3, n = 3, k = 2
Output: 4
See below diagram for four paths with 
maximum 2 turns.

Input:  m = 3, n = 3, k = 1
Output: 2 

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.
Эта задача может быть рекурсивно вычислена с использованием приведенной ниже рекурсивной формулы.

countPaths(i, j, k): Count of paths to reach (i,j) from (0, 0)
countPathsDir(i, j, k, 0): Count of paths if we reach (i, j) 
                           along row. 
countPathsDir(i, j, k, 1): Count of paths if we reach (i, j) 
                           along column. 
The fourth parameter in countPathsDir() indicates direction.

Value of countPaths() can be written as:
countPaths(i, j, k) = countPathsDir(i, j, k, 0) + 
                      countPathsDir(i, j, k, 1) 

And value of  countPathsDir() can be recursively defined as:

// Base cases

// If current direction is along row
If (d == 0) 
  // Count paths for two cases
  // 1) We reach here through previous row.
  // 2) We reach here through previous column, so number of 
  //    turns k reduce by 1.
  countPathsDir(i, j, k, d) = countPathsUtil(i, j-1, k, d) +
                              countPathsUtil(i-1, j, k-1, !d);

// If current direction is along column
Else 
  // Similar to above
  countPathsDir(i, j, k, d) =  countPathsUtil(i-1, j, k, d) +
                               countPathsUtil(i, j-1, k-1, !d);

Мы можем решить эту проблему за полиномиальное время, используя динамическое программирование. Идея состоит в том, чтобы использовать четырехмерную таблицу dp [m] [n] [k] [d], где m — количество строк, n — количество столбцов, k — количество разрешенных поворотов, а d — направление.

Ниже приведена реализация на основе динамического программирования.

C ++

// C ++ программа для подсчета количества путей с максимумом
// k ходов разрешено
#include<bits/stdc++.h>

using namespace std;

#define MAX 100

  
// таблица для хранения результатов подзадач

int dp[MAX][MAX][MAX][2];

  
// Возвращает количество путей для достижения (i, j) из (0, 0)
// используя не более k оборотов. d текущее направление
// d = 0 указывает вдоль строки, d = 1 указывает вдоль
// столбец.

int countPathsUtil(int i, int j, int k, int d)

{

    // Если недопустимые индексы строки или столбца

    if (i < 0 || j < 0)

        return 0;

  

    // Если текущая ячейка вверху слева

    if (i == 0 && j == 0)

        return 1;

  

    // Если 0 поворачивает налево

    if (k == 0)

    {

        // Если направление это строка, то мы можем достичь здесь

        // только если направление - строка, а строка - 0.

        if (d == 0 && i == 0) return 1;

  

        // Если направление является столбцом, то мы можем достичь здесь

        // только если направление - это столбец, а столбец - 0.

        if (d == 1 && j == 0) return 1;

  

        return 0;

    }

  

    // Если эта подзадача уже оценена

    if (dp[i][j][k][d] != -1)

        return dp[i][j][k][d];

  

    // Если текущим направлением является строка, то считать пути для двух случаев

    // 1) Мы достигаем здесь через предыдущий ряд.

    // 2) Мы достигаем здесь через предыдущий столбец, поэтому число

    // повороты k уменьшают на 1.

    if (d == 0)

      return dp[i][j][k][d] = countPathsUtil(i, j-1, k, d) +

                              countPathsUtil(i-1, j, k-1, !d);

  

    // Аналогично выше, если направление является столбцом

    return dp[i][j][k][d] =  countPathsUtil(i-1, j, k, d) +

                             countPathsUtil(i, j-1, k-1, !d);

}

  
// Эта функция в основном инициализирует массив 'dp' как -1 и вызывает
// countPathsUtil ()

int countPaths(int i, int j, int k)

{

    // Если (0, 0) сама цель

    if (i == 0 && j == 0)

          return 1;

  

    // Инициализируем массив 'dp'

    memset(dp, -1, sizeof dp);

  

    // Повторение для двух случаев: перемещение по строке и по столбцу

    return countPathsUtil(i-1, j, k, 1) +  // Перемещение по ряду

           countPathsUtil(i, j-1, k, 0); // Перемещение по столбцу

}

  
// Драйвер программы

int main()

{

    int m = 3, n = 3, k = 2;

    cout << "Number of paths is "

         << countPaths(m-1, n-1, k) << endl;

    return 0;

}

Джава

// Java-программа для подсчета количества путей
// с максимальным разрешенным ходом

import java.util.*;

class GFG

{

static int MAX = 100;

  
// таблица для хранения результатов подзадач

static int [][][][]dp = new int[MAX][MAX][MAX][2]; 

  
// Возвращает количество путей для достижения (i, j) из (0, 0)
// используя не более k оборотов. d текущее направление
// d = 0 указывает вдоль строки, d = 1 указывает вдоль
// столбец.

static int countPathsUtil(int i, int j, int k, int d) 

    // Если недопустимые индексы строки или столбца

    if (i < 0 || j < 0

        return 0

  

    // Если текущая ячейка вверху слева

    if (i == 0 && j == 0

        return 1

  

    // Если 0 поворачивает налево

    if (k == 0

    

        // Если направление это строка, то мы можем достичь здесь

        // только если направление - строка, а строка - 0.

        if (d == 0 && i == 0) return 1

  

        // Если направление является столбцом, то мы можем достичь здесь

        // только если направление - это столбец, а столбец - 0.

        if (d == 1 && j == 0) return 1

  

        return 0

    

  

    // Если эта подзадача уже оценена

    if (dp[i][j][k][d] != -1

        return dp[i][j][k][d]; 

  

    // Если текущим направлением является строка,

    // затем подсчитываем пути для двух случаев

    // 1) Мы достигаем здесь через предыдущий ряд.

    // 2) Мы достигаем здесь через предыдущий столбец,

    // поэтому число витков k уменьшается на 1.

    if (d == 0

    return dp[i][j][k][d] = countPathsUtil(i, j - 1, k, d) + 

                            countPathsUtil(i - 1, j, k - 1, d == 1 ? 0 : 1); 

  

    // Аналогично выше, если направление является столбцом

    return dp[i][j][k][d] = countPathsUtil(i - 1, j, k, d) + 

                            countPathsUtil(i, j - 1, k - 1, d == 1 ? 0 : 1); 

  
// Эта функция в основном инициализирует массив 'dp'
// как -1 и вызывает countPathsUtil ()

static int countPaths(int i, int j, int k) 

    // Если (0, 0) сама цель

    if (i == 0 && j == 0

        return 1

  

    // Инициализируем массив 'dp'

    for(int p = 0; p < MAX; p++)

    {

        for(int q = 0; q < MAX; q++)

        {

            for(int r = 0; r < MAX; r++)

                for(int s = 0; s < 2; s++)

                    dp[p][q][r][s] = -1;

        }

    }

  

    // Повторение для двух случаев: перемещение по строке и по столбцу

    return countPathsUtil(i - 1, j, k, 1) + // Перемещение по ряду

        countPathsUtil(i, j - 1, k, 0); // Перемещение по столбцу

  
// Код драйвера

public static void main(String[] args)

{

    int m = 3, n = 3, k = 2

    System.out.println("Number of paths is "

                 countPaths(m - 1, n - 1, k)); 

}
}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python3 программа для подсчета количества путей
# с максимально разрешенным к поворотам

MAX = 100

  
# таблица для хранения результатов подзадач

dp = [[[[-1 for col in range(2)]

            for col in range(MAX)] 

            for row in range(MAX)] 

            for row in range(MAX)]

  
# Возвращает количество путей для достижения
# (i, j) из (0, 0), используя не более k оборотов.
# d - текущее направление, d = 0 указывает
# вдоль строки, d = 1 указывает вдоль столбца.

def countPathsUtil(i, j, k, d):

  

    # Если недопустимы индексы строки или столбца

    if (i < 0 or j < 0):

        return 0

  

    # Если текущая ячейка сверху слева

    if (i == 0 and j == 0):

        return 1

  

    # Если 0 поворачивает налево

    if (k == 0):

      

        # Если направление - строка, то мы можем достичь здесь

        # только если направление - строка, а строка - 0.

        if (d == 0 and i == 0):

            return 1

  

        # Если направление - это столбец, то мы можем достичь здесь

        # только если направление - это столбец, а столбец - 0.

        if (d == 1 and j == 0):

            return 1

  

        return 0

      

    # Если эта подзадача уже оценена

    if (dp[i][j][k][d] != -1):

        return dp[i][j][k][d]

  

    # Если текущим направлением является строка,

    # затем посчитать пути для двух случаев

    # 1) Мы достигаем здесь через предыдущий ряд.

    # 2) Мы достигаем здесь через предыдущий столбец,

    # количество ходов k уменьшается на 1.

    if (d == 0):

        dp[i][j][k][d] = countPathsUtil(i, j - 1, k, d) + \

                         countPathsUtil(i - 1, j, k - 1, not d)

        return dp[i][j][k][d]

  

    # Аналогично приведенному выше, если направление является столбцом

    dp[i][j][k][d] = countPathsUtil(i - 1, j, k, d) + \

                     countPathsUtil(i, j - 1, k - 1, not d)

    return dp[i][j][k][d]

  
# Эта функция в основном инициализирует массив 'dp'
# как -1 и вызывает countPathsUtil ()

def countPaths(i, j, k):

  

    # Если (0, 0) сама цель

    if (i == 0 and j == 0):

        return 1

  

    # Повторить для двух случаев: перемещение по ряду

    # и вдоль столбца

    return countPathsUtil(i - 1, j, k, 1) +\

           countPathsUtil(i, j - 1, k, 0)

  
Код водителя

if __name__ == '__main__':

    m = 3

    n = 3

    k = 2

    print("Number of paths is"

           countPaths(m - 1, n - 1, k))

  
# Этот код предоставлен Ashutosh450

C #

// C # программа для подсчета количества путей
// с максимальным разрешенным ходом

using System;

  

class GFG

{

static int MAX = 100;

  
// таблица для хранения результатов подзадач

static int [,,,]dp = new int[MAX, MAX, MAX, 2]; 

  
// Возвращает количество путей для достижения (i, j) из (0, 0)
// используя не более k оборотов. d текущее направление
// d = 0 указывает вдоль строки, d = 1 указывает вдоль
// столбец.

static int countPathsUtil(int i, int j, int k, int d) 

    // Если недопустимые индексы строки или столбца

    if (i < 0 || j < 0) 

        return 0; 

  

    // Если текущая ячейка вверху слева

    if (i == 0 && j == 0) 

        return 1; 

  

    // Если 0 поворачивает налево

    if (k == 0) 

    

        // Если направление это строка, то мы можем достичь здесь

        // только если направление - строка, а строка - 0.

        if (d == 0 && i == 0) return 1; 

  

        // Если направление является столбцом, то мы можем достичь здесь

        // только если направление - это столбец, а столбец - 0.

        if (d == 1 && j == 0) return 1; 

  

        return 0; 

    

  

    // Если эта подзадача уже оценена

    if (dp[i, j, k, d] != -1) 

        return dp[i, j, k, d]; 

  

    // Если текущим направлением является строка,

    // затем подсчитываем пути для двух случаев

    // 1) Мы достигаем здесь через предыдущий ряд.

    // 2) Мы достигаем здесь через предыдущий столбец,

    // поэтому число витков k уменьшается на 1.

    if (d == 0) 

    return dp[i, j, k, d] = countPathsUtil(i, j - 1, k, d) + 

                            countPathsUtil(i - 1, j, k - 1,

                                            d == 1 ? 0 : 1); 

  

    // Аналогично выше, если направление является столбцом

    return dp[i, j, k, d] = countPathsUtil(i - 1, j, k, d) + 

                            countPathsUtil(i, j - 1, k - 1, 

                                            d == 1 ? 0 : 1); 

  
// Эта функция в основном инициализирует массив 'dp'
// как -1 и вызывает countPathsUtil ()

static int countPaths(int i, int j, int k) 

    // Если (0, 0) сама цель

    if (i == 0 && j == 0) 

        return 1; 

  

    // Инициализируем массив 'dp'

    for(int p = 0; p < MAX; p++)

    {

        for(int q = 0; q < MAX; q++)

        {

            for(int r = 0; r < MAX; r++)

                for(int s = 0; s < 2; s++)

                    dp[p, q, r, s] = -1;

        }

    }

  

    // Повторение для двух случаев: перемещение по строке и по столбцу

    return countPathsUtil(i - 1, j, k, 1) + // Перемещение по ряду

           countPathsUtil(i, j - 1, k, 0); // Перемещение по столбцу

  
// Код драйвера

public static void Main(String[] args)

{

    int m = 3, n = 3, k = 2; 

    Console.WriteLine("Number of paths is "

                countPaths(m - 1, n - 1, k)); 

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Number of paths is 4

Временная сложность вышеуказанного решения составляет O (m * n * k)

Спасибо Gaurav Ahirwar за то, что он предложил это решение.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитайте количество путей с не более чем k поворотами

0.00 (0%) 0 votes