Рубрики

Соберите максимум монет, прежде чем попасть в тупик

Дана матрица символов, в которой каждая ячейка имеет одно из следующих значений.

'C' -->  This cell has coin

'#' -->  This cell is a blocking cell. 
         We can not go anywhere from this.

'E' -->  This cell is empty. We don't get
         a coin, but we can move from here.  

Начальная позиция — ячейка (0, 0), а начальное направление — правильное.

Ниже приведены правила для перемещения через клетки.

Если лицо правильно, то мы можем перейти к клеткам ниже

  1. Переместитесь на один шаг вперед, т.е. ячейка (i, j + 1) и направление останутся правыми.
  2. Переместитесь на один шаг вниз и поверните влево, т.е. ячейка (i + 1, j) и направление станет левым.
  3. Если лицо слева, то мы можем перейти к клеткам ниже

    1. Переместитесь на один шаг вперед, т.е. ячейка (i, j-1) и направление останутся левыми.
    2. Переместитесь на один шаг вниз и поверните направо, т.е. ячейка (i + 1, j) и направление станут правильными.

    Конечная позиция может быть где угодно, а конечное направление может быть любым. Цель состоит в том, чтобы собрать максимум монет.

    Пример:

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

    Вышеупомянутая проблема может быть рекурсивно определена как ниже:

    maxCoins(i, j, d):  Maximum number of coins that can be 
                        collected if we begin at cell (i, j)
                        and direction d.
                        d can be either 0 (left) or 1 (right)
    
       // If this is a blocking cell, return 0. isValid() checks
       // if i and j are valid row and column indexes.
       If (arr[i][j] == '#' or isValid(i, j) == false)
           return 0
    
       // Initialize result
       If (arr[i][j] == 'C')
           result = 1;
       Else 
           result = 0;
    
       If (d == 0) // Left direction 
           return result +  max(maxCoins(i+1, j, 1),  // Down
                                maxCoins(i, j-1, 0)); // Ahead in left
    
       If (d == 1) // Right direction 
           return result +  max(maxCoins(i+1, j, 1),  // Down
                                maxCoins(i, j+1, 0)); // Ahead in right
    

    Ниже приведена реализация C ++ вышеупомянутого рекурсивного алгоритма.

    C ++

    // Наивная рекурсивная программа C ++ для поиска максимального количества монет
    // это можно собрать перед тем, как попасть в тупик
    #include<bits/stdc++.h>

    using namespace std;

    #define R 5
    #define C 5

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

    bool isValid(int i, int j)

    {

        return (i >=0 && i < R && j >=0 && j < C);

    }

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

    int maxCoinsRec(char arr[R][C],  int i, int j, int dir)

    {

        // Если это недопустимая ячейка или если ячейка является блокирующей ячейкой

        if (isValid(i,j) == false || arr[i][j] == '#')

            return 0;

      

        // Проверяем, содержит ли эта ячейка монету «C» или пустую «E».

        int result = (arr[i][j] == 'C')? 1: 0;

      

        // Получить максимум два случая, когда вы смотрите прямо в этой ячейке

        if (dir == 1) // Направление правильное

           return result + max(maxCoinsRec(arr, i+1, j, 0),     // Вниз

                                 maxCoinsRec(arr, i, j+1, 1));  // Впереди справа

      

        // Направление оставлено

        // Получить максимум два случая, когда вы смотрите влево в этой ячейке

         return  result + max(maxCoinsRec(arr, i+1, j, 1),    // Вниз

                               maxCoinsRec(arr, i, j-1, 0));  // Впереди слева

    }

      
    // Программа драйвера для проверки вышеуказанной функции

    int main()

    {

        char arr[R][C] = { {'E', 'C', 'C', 'C', 'C'},

                           {'C', '#', 'C', '#', 'E'},

                           {'#', 'C', 'C', '#', 'C'},

                           {'C', 'E', 'E', 'C', 'E'},

                           {'C', 'E', '#', 'C', 'E'}

                         };

      

       // В соответствии с вопросом начальная ячейка (0, 0) и направление

        // право

        cout << "Maximum number of collected coins is "

             << maxCoinsRec(arr, 0, 0, 1);

      

        return 0;

    }

    python3

    # Наивная рекурсивная программа Python 3 для
    # найти максимальное количество монет
    # которые можно собрать перед тем, как попасть в тупик

    R= 5

    C= 5

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

    def isValid( i, j): 

      

        return (i >=0 and i < R and j >=0 and j < C) 

      

      
    # dir = 0 для левой стороны, dir = 1 для правой стороны.
    # Эта функция возвращает
    # количество максимальных монет, которые можно собрать
    # начиная с (i, j).

    def maxCoinsRec(arr, i, j, dir): 

      

        # Если это недопустимая ячейка или если ячейка является блокирующей ячейкой

        if (isValid(i,j) == False or arr[i][j] == '#'): 

            return 0

      

        # Проверьте, содержит ли эта ячейка монету «C» или пустую «E».

        if (arr[i][j] == 'C'):

            result=1

        else:

            result=0

      

        # Получите максимум два случая, когда вы находитесь прямо в этой ячейке

        if (dir == 1):

              

         # Направление правильное

            return (result + max(maxCoinsRec(arr, i+1, j, 0),

                   maxCoinsRec(arr, i, j+1, 1))) 

      

        # Направление осталось

        # Получите максимум два случая, когда вы смотрите влево в этой ячейке

        return (result + max(maxCoinsRec(arr, i+1, j, 1),

               maxCoinsRec(arr, i, j-1, 0))) 

      

      
    # Программа драйвера для проверки вышеуказанной функции

    if __name__=='__main__':

        arr = [ ['E', 'C', 'C', 'C', 'C'],

              ['C', '#', 'C', '#', 'E'],

              ['#', 'C', 'C', '#', 'C'],

              ['C', 'E', 'E', 'C', 'E'],

              ['C', 'E', '#', 'C', 'E'] ] 

      

        # В соответствии с вопросом начальная ячейка (0, 0) и направление

        # право

        print("Maximum number of collected coins is ", maxCoinsRec(arr, 0, 0, 1)) 

      
    # этот код предоставлен ash264


    Выход:

    Maximum number of collected coins is 8

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

    C ++

    // Программа на C ++ для динамического программирования, чтобы найти максимум
    // количество монет, которые можно собрать перед попаданием в
    // тупик
    #include<bits/stdc++.h>

    using namespace std;

    #define R 5
    #define C 5

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

    bool isValid(int i, int j)

    {

        return (i >=0 && i < R && j >=0 && j < C);

    }

      
    // dir = 0 для левого, dir = 1 для правого. Эта функция возвращает
    // максимальное количество монет, которое можно собрать, начиная с
    // (i, j).

    int maxCoinsUtil(char arr[R][C],  int i, int j, int dir,

                     int dp[R][C][2])

    {

        // Если это недопустимая ячейка или если ячейка является блокирующей ячейкой

        if (isValid(i,j) == false || arr[i][j] == '#')

            return 0;

      

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

        // уже оцененный ответ.

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

           return dp[i][j][dir];

      

        // Проверяем, содержит ли эта ячейка монету «C» или «E».

        dp[i][j][dir] = (arr[i][j] == 'C')? 1: 0;

      

        // Получаем максимум два случая, когда вы обращены вправо

        // в этой ячейке

        if (dir == 1) // Направление правильное

           dp[i][j][dir] += max(maxCoinsUtil(arr, i+1, j, 0, dp), // Вниз

                                maxCoinsUtil(arr, i, j+1, 1, dp)); // Впереди в rught

      

        // Получить максимум два случая, когда вы обращены влево

        // в этой ячейке

        if (dir == 0) // Направление оставлено

           dp[i][j][dir] += max(maxCoinsUtil(arr, i+1, j, 1, dp),  // Вниз

                                maxCoinsUtil(arr, i, j-1, 0, dp)); // Впереди слева

      

        // вернуть ответ

        return dp[i][j][dir];

    }

      
    // Эта функция в основном создает таблицу поиска и вызывает
    // maxCoinsUtil ()

    int maxCoins(char arr[R][C])

    {

        // Создать таблицу поиска и инициализировать все значения как -1

        int dp[R][C][2];

        memset(dp, -1, sizeof dp);

      

        // В соответствии с вопросом начальная ячейка (0, 0) и направление

        // правильно

        return maxCoinsUtil(arr, 0, 0, 1, dp);

    }

      
    // Программа драйвера для проверки вышеуказанной функции

    int main()

    {

        char arr[R][C] = { {'E', 'C', 'C', 'C', 'C'},

                           {'C', '#', 'C', '#', 'E'},

                           {'#', 'C', 'C', '#', 'C'},

                           {'C', 'E', 'E', 'C', 'E'},

                           {'C', 'E', '#', 'C', 'E'}

                         };

      

      

        cout << "Maximum number of collected coins is "

             << maxCoins(arr);

      

        return 0;

    }

    Выход:

    Maximum number of collected coins is 8

    Временная сложность вышеуказанного решения составляет O (R x C xd). Поскольку d равно 2, временную сложность можно записать как O (R x C).

    Спасибо Gaurav Ahirwar за предложенное выше решение.

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

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

    Соберите максимум монет, прежде чем попасть в тупик

    0.00 (0%) 0 votes