Рубрики

Подсчитайте количество способов добраться до места назначения в лабиринте

Учитывая лабиринт с препятствиями, подсчитайте количество путей, чтобы добраться до крайней правой нижней ячейки от самой верхней левой ячейки. Ячейка в данном лабиринте имеет значение -1, если это блокировка или тупик, иначе 0.

Из данной ячейки нам разрешено перемещаться только в ячейки (i + 1, j) и (i, j + 1).

Примеры:

Input: maze[R][C] =  {{0,  0, 0, 0},
                      {0, -1, 0, 0},
                      {-1, 0, 0, 0},
                      {0,  0, 0, 0}};
Output: 4
There are four possible paths as shown in
below diagram.

Эта проблема является расширением нижеприведенной проблемы.

Возвращение | Комплект 2 (Крыса в лабиринте)

В этом посте обсуждается другое решение, которое также может быть использовано для решения вышеуказанной Крысы в задаче Лабиринта.

Идея состоит в том, чтобы изменить заданную сетку [] [] так, чтобы сетка [i] [j] содержала количество путей для достижения (i, j) из (0, 0), если (i, j) не является блокировкой, иначе Сетка [I] [J] остается -1.

We can recursively compute grid[i][j] using below 
formula and finally return grid[R-1][C-1]

  // If current cell is a blockage
  if (maze[i][j] == -1)
      maze[i][j] = -1; //  Do not change

  // If we can reach maze[i][j] from maze[i-1][j]
  // then increment count.
  else if (maze[i-1][j] > 0)
      maze[i][j] = (maze[i][j] + maze[i-1][j]);

  // If we can reach maze[i][j] from maze[i][j-1]
  // then increment count.
  else if (maze[i][j-1] > 0)
      maze[i][j] = (maze[i][j] + maze[i][j-1]);

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std;

#define R 4
#define C 4

  
// Возвращает количество возможных путей в лабиринте [R] [C]
// от (0,0) до (R-1, C-1)

int countPaths(int maze[][C])

{

    // Если начальная ячейка заблокирована, нет

    // способ перемещения куда угодно

    if (maze[0][0]==-1)

        return 0;

  

    // Инициализация самого левого столбца

    for (int i=0; i<R; i++)

    {

        if (maze[i][0] == 0)

            maze[i][0] = 1;

  

        // Если мы встретим заблокированную ячейку слева

        // строка, нет возможности посетить любую ячейку

        // прямо под ним.

        else

            break;

    }

  

    // Аналогично инициализируем верхнюю строку

    for (int i=1; i<C; i++)

    {

        if (maze[0][i] == 0)

            maze[0][i] = 1;

  

        // Если мы столкнемся с заблокированной ячейкой в самой нижней части

        // строка, нет возможности посетить любую ячейку

        // прямо под ним.

        else

            break;

    }

  

    // Единственное отличие состоит в том, что если ячейка равна -1,

    // просто игнорируем это, иначе вычислим

    // посчитаем значение лабиринта [i] [j]

    for (int i=1; i<R; i++)

    {

        for (int j=1; j<C; j++)

        {

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

            if (maze[i][j] == -1)

                continue;

  

            // Если мы можем добраться до лабиринта [i] [j] из лабиринта [i-1] [j]

            // затем увеличить счетчик.

            if (maze[i-1][j] > 0)

                maze[i][j] = (maze[i][j] + maze[i-1][j]);

  

            // Если мы можем добраться до лабиринта [i] [j] из лабиринта [i] [j-1]

            // затем увеличить счетчик.

            if (maze[i][j-1] > 0)

                maze[i][j] = (maze[i][j] + maze[i][j-1]);

        }

    }

  

    // Если последняя ячейка заблокирована, выведите 0, в противном случае

    // ответ

    return (maze[R-1][C-1] > 0)? maze[R-1][C-1] : 0;

}

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

int main()

{

    int maze[R][C] =  {{0,  0, 0, 0},

                       {0, -1, 0, 0},

                       {-1, 0, 0, 0},

                       {0,  0, 0, 0}};

    cout << countPaths(maze);

    return 0;

}

Джава

// Java-программа для подсчета количества путей в лабиринте
// с препятствиями.

import java.io.*;

  

class GFG 

{

    static int R = 4;

    static int C = 4;

      

    // Возвращает количество возможных путей в

    // лабиринт [R] [C] от (0,0) до (R-1, C-1)

    static int countPaths(int maze[][])

    {

        // Если начальная ячейка заблокирована,

        // нет пути никуда

        if (maze[0][0]==-1)

            return 0;

      

        // Инициализация самого левого столбца

        for (int i = 0; i < R; i++)

        {

            if (maze[i][0] == 0)

                maze[i][0] = 1;

      

            // Если мы сталкиваемся с заблокированной ячейкой

            // в крайнем левом ряду нет пути

            // посещения любой клетки прямо под ней.

            else

                break;

        }

      

        // Аналогично инициализируем верхнюю строку

        for (int i =1 ; i< C ; i++)

        {

            if (maze[0][i] == 0)

                maze[0][i] = 1;

      

            // Если мы встретим заблокированную ячейку в

            // самый нижний ряд, нет способа

            // посещение любой клетки прямо под ней.

            else

                break;

        }

      

        // Разница лишь в том, что если ячейка

        // равен -1, просто игнорируем это иначе

        // вычисляем значение счетчика лабиринт [i] [j]

        for (int i = 1; i < R; i++)

        {

            for (int j = 1; j <C ; j++)

            {

                // Если блокировка найдена,

                // игнорируем эту ячейку

                if (maze[i][j] == -1)

                    continue;

      

                // Если мы можем добраться до лабиринта [i] [j] из

                // лабиринт [i-1] [j] затем увеличиваем счетчик.

                if (maze[i - 1][j] > 0)

                    maze[i][j] = (maze[i][j] + 

                                 maze[i - 1][j]);

      

                // Если мы можем добраться до лабиринта [i] [j] из

                // лабиринт [i] [j-1] затем увеличиваем счетчик.

                if (maze[i][j - 1] > 0)

                    maze[i][j] = (maze[i][j] + 

                                  maze[i][j - 1]);

            }

        }

      

        // Если последняя ячейка заблокирована,

        // выводим 0, иначе ответ

        return (maze[R - 1][C - 1] > 0) ? 

                maze[R - 1][C - 1] : 0;

    }

      

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

  

    public static void main (String[] args) 

    {

        int maze[][] = {{0, 0, 0, 0},

                       {0, -1, 0, 0},

                       {-1, 0, 0, 0},

                       {0, 0, 0, 0}};

        System.out.println (countPaths(maze));

      

    }

  
}

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

python3

# Python 3 программа для подсчета количества путей
# в лабиринте с препятствиями.

  

R = 4

C = 4

  
# Возвращает количество возможных путей в
# лабиринт [R] [C] от (0,0) до (R-1, C-1)

def countPaths(maze):

      

    # Если начальная ячейка заблокирована,

    # нет способа никуда двигаться

    if (maze[0][0] == -1):

        return 0

  

    # Инициализация самого левого столбца

    for i in range(R):

        if (maze[i][0] == 0):

            maze[i][0] = 1

  

        # Если мы столкнемся с заблокированной ячейкой в

        # крайний левый ряд, нет способа

        # посещение любой клетки прямо под ней.

        else:

            break

  

    # Аналогично инициализируем верхнюю строку

    for i in range(1, C, 1):

        if (maze[0][i] == 0):

            maze[0][i] = 1

  

        # Если мы столкнемся с заблокированной ячейкой в

        # самый нижний ряд, нет способа

        # посещение любой клетки прямо под ней.

        else:

            break

  

    # Единственное отличие состоит в том, что если ячейка равна -1,

    # просто игнорировать это, иначе вычислить

    # значение счетчика лабиринт [i] [j]

    for i in range(1, R, 1):

        for j in range(1, C, 1):

              

            # Если блокировка найдена, игнорируйте эту ячейку

            if (maze[i][j] == -1):

                continue

  

            # Если мы сможем добраться до лабиринта [i] [j] из

            # лабиринт [i-1] [j] затем увеличьте счетчик.

            if (maze[i - 1][j] > 0):

                maze[i][j] = (maze[i][j] +

                              maze[i - 1][j])

  

            # Если мы сможем добраться до лабиринта [i] [j] из

            # лабиринт [я] [J-1] затем увеличить счетчик.

            if (maze[i][j - 1] > 0):

                maze[i][j] = (maze[i][j] +

                              maze[i][j - 1])

  

    # Если последняя ячейка заблокирована,

    # выведите 0, иначе ответ

    if (maze[R - 1][C - 1] > 0):

        return maze[R - 1][C - 1

    else:

        return 0

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

if __name__ == '__main__':

    maze = [[0, 0, 0, 0],

            [0, -1, 0, 0],

            [-1, 0, 0, 0],

            [0, 0, 0, 0 ]]

    print(countPaths(maze))

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

C #

// C # программа для подсчета количества путей в лабиринте
// с препятствиями.

using System;

  

class GFG {

      

    static int R = 4;

    static int C = 4;

      

    // Возвращает количество возможных путей в

    // лабиринт [R] [C] от (0,0) до (R-1, C-1)

    static int countPaths(int [,]maze)

    {

          

        // Если начальная ячейка заблокирована,

        // нет пути никуда

        if (maze[0,0]==-1)

            return 0;

      

        // Инициализация самого левого столбца

        for (int i = 0; i < R; i++)

        {

            if (maze[i,0] == 0)

                maze[i,0] = 1;

      

            // Если мы сталкиваемся с заблокированной ячейкой

            // в крайнем левом ряду нет пути

            // посещения любой клетки прямо под ней.

            else

                break;

        }

      

        // Аналогично инициализируем верхнюю строку

        for (int i =1 ; i< C ; i++)

        {

            if (maze[0,i] == 0)

                maze[0,i] = 1;

      

            // Если мы встретим заблокированную ячейку в

            // самый нижний ряд, нет способа

            // посещение любой клетки прямо под ней.

            else

                break;

        }

      

        // Разница лишь в том, что если ячейка

        // равен -1, просто игнорируем это иначе

        // вычисляем значение счетчика лабиринт [i] [j]

        for (int i = 1; i < R; i++)

        {

            for (int j = 1; j <C ; j++)

            {

                // Если блокировка найдена,

                // игнорируем эту ячейку

                if (maze[i,j] == -1)

                    continue;

      

                // Если мы можем добраться до лабиринта [i] [j] из

                // лабиринт [i-1] [j] затем увеличиваем счетчик.

                if (maze[i - 1,j] > 0)

                    maze[i,j] = (maze[i,j] + 

                                maze[i - 1,j]);

      

                // Если мы можем добраться до лабиринта [i] [j] из

                // лабиринт [i] [j-1] затем увеличиваем счетчик.

                if (maze[i,j - 1] > 0)

                    maze[i,j] = (maze[i,j] + 

                                maze[i,j - 1]);

            }

        }

      

        // Если последняя ячейка заблокирована,

        // выводим 0, иначе ответ

        return (maze[R - 1,C - 1] > 0) ? 

                maze[R - 1,C - 1] : 0;

    }

      

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

    public static void Main () 

    {

        int [,]maze = { {0, 0, 0, 0},

                        {0, -1, 0, 0},

                        {-1, 0, 0, 0},

                        {0, 0, 0, 0}};

                          

        Console.Write (countPaths(maze));

    }

  
}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для подсчета числа
// дорожек в лабиринте с препятствиями.

  

$R = 4;

$C = 4;

  
// Возвращает количество возможных
// пути в лабиринте [R] [C]
// от (0,0) до (R-1, C-1)

function countPaths( $maze)

{

    global $R, $C;

      

    // Если начальная ячейка

    // заблокирован, нет

    // способ перемещения куда угодно

    if ($maze[0][0] == - 1)

        return 0;

  

    // Инициализация

    // крайний левый столбец

    for ( $i = 0; $i < $R; $i++)

    {

        if ($maze[$i][0] == 0)

            $maze[$i][0] = 1;

  

        // Если мы столкнулись с заблокированным

        // ячейка в крайнем левом ряду,

        // нет способа

        // посещение любой клетки

        // прямо под ним.

        else

            break;

    }

  

    // Аналогично инициализируем

    // самый верхний ряд

    for($i = 1; $i < $C; $i++)

    {

        if ($maze[0][$i] == 0)

            $maze[0][$i] = 1;

  

        // Если мы столкнулись с заблокированным

        // ячейка в самом нижнем ряду,

        // нет способа

        // посещение любой клетки

        // прямо под ним.

        else

            break;

    }

  

    // Единственная разница

    // что если ячейка равна -1,

    // просто игнорируем это

    // рекурсивно вычислить

    // посчитаем значение лабиринта [i] [j]

    for($i = 1; $i < $R; $i++)

    {

        for($j = 1; $j < $C; $j++)

        {

              

            // Если блокировка найдена,

            // игнорируем эту ячейку

            if ($maze[$i][$j] == -1)

                continue;

  

            // Если мы сможем добраться до лабиринта [i] [j]

            // из лабиринта [i-1] [j]

            // затем увеличить счетчик.

            if ($maze[$i - 1][$j] > 0)

                $maze[$i][$j] = ($maze[$i][$j] + 

                           $maze[$i - 1][$j]);

  

            // Если мы сможем добраться до лабиринта [i] [j]

            // из лабиринта [i] [j-1]

            // затем увеличить счетчик.

            if ($maze[$i][$j - 1] > 0)

                $maze[$i][$j] = ($maze[$i][$j] + 

                             $maze[$i][$j - 1]);

        }

    }

  

    // Если последняя ячейка

    // заблокирован, вывод 0,

    // иначе ответ

    return ($maze[$R - 1][$C - 1] > 0) ?

            $maze[$R - 1][$C - 1] : 0;

}

  

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

    $maze = array(array(0, 0, 0, 0),

                  array(0, -1, 0, 0),

                  array(-1, 0, 0, 0),

                  array(0, 0, 0, 0));

    echo countPaths($maze);

  
// Этот код предоставлен anuj_67.
?>


Выход:

4

Сложность времени: O (R x C)

Эта статья предоставлена Рошни Агарвал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Подсчитайте количество способов добраться до места назначения в лабиринте

0.00 (0%) 0 votes