Cuente el número de formas de llegar al destino en un laberinto

Dado un laberinto de celdas 0 y -1, la tarea es encontrar todos los caminos desde (0, 0) hasta (n-1, m-1), y cada camino debe pasar por al menos una celda que contenga -1. Desde una celda dada, podemos movernos a las celdas (i+1, j) y (i, j+1) solamente. 
Este problema es una variación del problema publicado aquí .
Ejemplos: 
 

Entrada: laberinto[][] = { 
{0, 0, 0, 0}, 
{0, -1, 0, 0}, 
{-1, 0, 0, 0}, 
{0, 0, 0, 0} } 
Salida: 16 
 

Enfoque: Para encontrar todos los caminos que pasan por al menos una celda marcada (celda que contiene -1). Si encontramos los caminos que no pasan por ninguna de las celdas marcadas y todos los caminos posibles desde (0, 0) hasta (n-1, m-1) entonces podemos encontrar todos los caminos que pasan por al menos una de las celdas de las marcas. 
Número de caminos que pasan por al menos una celda marcada = (Número total de caminos – Número de caminos que no pasan por ninguna celda marcada) 
Usaremos el enfoque mencionado en este artículo para encontrar el número total de caminos que no pasan a través de cualquier celda marcada y el número total de rutas desde el origen hasta el destino será (m + n – 2)! / (n – 1)! * (m – 1)! donde m y n son el número de filas y columnas. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
 
// Function to return the count of possible paths
// in a maze[R][C] from (0, 0) to (R-1, C-1) that
// do not pass through any of the marked cells
int countPaths(int maze[][C])
{
    // If the initial cell is blocked, there is no
    // way of moving anywhere
    if (maze[0][0] == -1)
        return 0;
 
    // Initializing the leftmost column
    for (int i = 0; i < R; i++) {
        if (maze[i][0] == 0)
            maze[i][0] = 1;
 
        // If we encounter a blocked cell in leftmost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // Similarly initialize the topmost row
    for (int i = 1; i < C; i++) {
        if (maze[0][i] == 0)
            maze[0][i] = 1;
 
        // If we encounter a blocked cell in bottommost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // The only difference is that if a cell is -1,
    // simply ignore it else recursively compute
    // count value maze[i][j]
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++) {
            // If blockage is found, ignore this cell
            if (maze[i][j] == -1)
                continue;
 
            // If we can reach maze[i][j] from maze[i-1][j]
            // then increment count.
            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.
            if (maze[i][j - 1] > 0)
                maze[i][j] = (maze[i][j] + maze[i][j - 1]);
        }
    }
 
    // If the final cell is blocked, output 0, otherwise
    // the answer
    return (maze[R - 1][C - 1] > 0) ? maze[R - 1][C - 1] : 0;
}
// Function to return the count of all possible
// paths from (0, 0) to (n - 1, m - 1)
int numberOfPaths(int m, int n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    int path = 1;
    for (int i = n; i < (m + n - 1); i++) {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
 
// Function to return the total count of paths
// from (0, 0) to (n - 1, m - 1) that pass
// through at least one of the marked cells
int solve(int maze[][C])
{
 
    // Total count of paths - Total paths that do not
    // pass through any of the marked cell
    int ans = numberOfPaths(R, C) - countPaths(maze);
 
    // return answer
    return ans;
}
 
// Driver code
int main()
{
    int maze[R][C] = { { 0, 0, 0, 0 },
                       { 0, -1, 0, 0 },
                       { -1, 0, 0, 0 },
                       { 0, 0, 0, 0 } };
 
    cout << solve(maze);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
static int R = 4;
static int C = 4;
 
// Function to return the count of possible paths
// in a maze[R][C] from (0, 0) to (R-1, C-1) that
// do not pass through any of the marked cells
static int countPaths(int maze[][])
{
     
    // If the initial cell is blocked,
    // there is no way of moving anywhere
    if (maze[0][0] == -1)
        return 0;
 
    // Initializing the leftmost column
    for (int i = 0; i < R; i++)
    {
        if (maze[i][0] == 0)
            maze[i][0] = 1;
 
        // If we encounter a blocked cell in leftmost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // Similarly initialize the topmost row
    for (int i = 1; i < C; i++)
    {
        if (maze[0][i] == 0)
            maze[0][i] = 1;
 
        // If we encounter a blocked cell in bottommost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // The only difference is that if a cell is -1,
    // simply ignore it else recursively compute
    // count value maze[i][j]
    for (int i = 1; i < R; i++)
    {
        for (int j = 1; j < C; j++)
        {
             
            // If blockage is found, ignore this cell
            if (maze[i][j] == -1)
                continue;
 
            // If we can reach maze[i][j] from
            //  maze[i-1][j] then increment count.
            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.
            if (maze[i][j - 1] > 0)
                maze[i][j] = (maze[i][j] +
                              maze[i][j - 1]);
        }
    }
 
    // If the final cell is blocked,
    // output 0, otherwise the answer
    return (maze[R - 1][C - 1] > 0) ?
                 maze[R - 1][C - 1] : 0;
}
 
// Function to return the count of all possible
// paths from (0, 0) to (n - 1, m - 1)
static int numberOfPaths(int m, int n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    int path = 1;
    for (int i = n; i < (m + n - 1); i++)
    {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
 
// Function to return the total count of paths
// from (0, 0) to (n - 1, m - 1) that pass
// through at least one of the marked cells
static int solve(int maze[][])
{
 
    // Total count of paths - Total paths that do not
    // pass through any of the marked cell
    int ans = numberOfPaths(R, C) - countPaths(maze);
 
    // return answer
    return ans;
}
 
// Driver code
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(solve(maze));
}
}
 
// This code is contributed by anuj_67..

# Python3 implementation of the approach
R = 4
C = 4
 
# Function to return the count of
# possible paths in a maze[R][C]
# from (0, 0) to (R-1, C-1) that
# do not pass through any of
# the marked cells
def countPaths(maze):
     
    # If the initial cell is blocked,
    # there is no way of moving anywhere
    if (maze[0][0] == -1):
        return 0
 
    # Initializing the leftmost column
    for i in range(R):
        if (maze[i][0] == 0):
            maze[i][0] = 1
 
        # If we encounter a blocked cell
        # in leftmost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # Similarly initialize the topmost row
    for i in range(1, C):
        if (maze[0][i] == 0):
            maze[0][i] = 1
 
        # If we encounter a blocked cell in
        # bottommost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # The only difference is that if
    # a cell is -1, simply ignore it
    # else recursively compute
    # count value maze[i][j]
    for i in range(1, R):
        for j in range(1, C):
             
            # If blockage is found,
            # ignore this cell
            if (maze[i][j] == -1):
                continue
 
            # If we can reach maze[i][j] from
            # maze[i-1][j] then increment count.
            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.
            if (maze[i][j - 1] > 0):
                maze[i][j] = (maze[i][j] +
                              maze[i][j - 1])
 
    # If the final cell is blocked,
    # output 0, otherwise the answer
    if (maze[R - 1][C - 1] > 0):
        return maze[R - 1][C - 1]
    else:
        return 0
 
# Function to return the count of
# all possible paths from
# (0, 0) to (n - 1, m - 1)
def numberOfPaths(m, n):
 
    # We have to calculate m+n-2 C n-1 here
    # which will be (m+n-2)! / (n-1)! (m-1)!
    path = 1
    for i in range(n, m + n - 1):
 
        path *= i
        path //= (i - n + 1)
 
    return path
 
# Function to return the total count
# of paths from (0, 0) to (n - 1, m - 1)
# that pass through at least one
# of the marked cells
def solve(maze):
     
    # Total count of paths - Total paths
    # that do not pass through any of
    # the marked cell
    ans = (numberOfPaths(R, C) -
           countPaths(maze))
 
    # return answer
    return ans
 
# Driver code
maze = [[ 0, 0, 0, 0 ],
        [ 0, -1, 0, 0 ],
        [ -1, 0, 0, 0 ],
        [ 0, 0, 0, 0 ]]
 
print(solve(maze))
 
# This code is contributed
# by Mohit Kumar

// C# implementation of the approach
using System;
class GFG
{
static int R = 4;
static int C = 4;
 
// Function to return the count of possible paths
// in a maze[R][C] from (0, 0) to (R-1, C-1) that
// do not pass through any of the marked cells
static int countPaths(int [,]maze)
{
     
    // If the initial cell is blocked,
    // there is no way of moving anywhere
    if (maze[0, 0] == -1)
        return 0;
 
    // Initializing the leftmost column
    for (int i = 0; i < R; i++)
    {
        if (maze[i, 0] == 0)
            maze[i, 0] = 1;
 
        // If we encounter a blocked cell in leftmost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // Similarly initialize the topmost row
    for (int i = 1; i < C; i++)
    {
        if (maze[0, i] == 0)
            maze[0, i] = 1;
 
        // If we encounter a blocked cell in
        // bottommost row, there is no way of
        // visiting any cell directly below it.
        else
            break;
    }
 
    // The only difference is that if a cell is -1,
    // simply ignore it else recursively compute
    // count value maze[i][j]
    for (int i = 1; i < R; i++)
    {
        for (int j = 1; j < C; j++)
        {
             
            // If blockage is found, ignore this cell
            if (maze[i, j] == -1)
                continue;
 
            // If we can reach maze[i][j] from
            // maze[i-1][j] then increment count.
            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.
            if (maze[i, j - 1] > 0)
                maze[i, j] = (maze[i, j] +
                              maze[i, j - 1]);
        }
    }
 
    // If the final cell is blocked,
    // output 0, otherwise the answer
    return (maze[R - 1, C - 1] > 0) ?
            maze[R - 1, C - 1] : 0;
}
 
// Function to return the count of all possible
// paths from (0, 0) to (n - 1, m - 1)
static int numberOfPaths(int m, int n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    int path = 1;
    for (int i = n; i < (m + n - 1); i++)
    {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
 
// Function to return the total count of paths
// from (0, 0) to (n - 1, m - 1) that pass
// through at least one of the marked cells
static int solve(int [,]maze)
{
 
    // Total count of paths - Total paths that do not
    // pass through any of the marked cell
    int ans = numberOfPaths(R, C) -
              countPaths(maze);
 
    // return answer
    return ans;
}
 
// Driver code
public static void Main ()
{
    int [,]maze = {{ 0, 0, 0, 0 },
                   { 0, -1, 0, 0 },
                   { -1, 0, 0, 0 },
                   { 0, 0, 0, 0 }};
 
    Console.Write(solve(maze));
}
}
 
// This code is contributed by anuj_67..

<script>
 
 
// Javascript implementation of the approach
var R = 4
var C = 4
 
// Function to return the count of possible paths
// in a maze[R][C] from (0, 0) to (R-1, C-1) that
// do not pass through any of the marked cells
function countPaths(maze)
{
    // If the initial cell is blocked, there is no
    // way of moving anywhere
    if (maze[0][0] == -1)
        return 0;
 
    // Initializing the leftmost column
    for (var i = 0; i < R; i++) {
        if (maze[i][0] == 0)
            maze[i][0] = 1;
 
        // If we encounter a blocked cell in leftmost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // Similarly initialize the topmost row
    for (var i = 1; i < C; i++) {
        if (maze[0][i] == 0)
            maze[0][i] = 1;
 
        // If we encounter a blocked cell in bottommost
        // row, there is no way of visiting any cell
        // directly below it.
        else
            break;
    }
 
    // The only difference is that if a cell is -1,
    // simply ignore it else recursively compute
    // count value maze[i][j]
    for (var i = 1; i < R; i++) {
        for (var j = 1; j < C; j++) {
            // If blockage is found, ignore this cell
            if (maze[i][j] == -1)
                continue;
 
            // If we can reach maze[i][j] from maze[i-1][j]
            // then increment count.
            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.
            if (maze[i][j - 1] > 0)
                maze[i][j] = (maze[i][j] + maze[i][j - 1]);
        }
    }
 
    // If the final cell is blocked, output 0, otherwise
    // the answer
    return (maze[R - 1][C - 1] > 0) ? maze[R - 1][C - 1] : 0;
}
// Function to return the count of all possible
// paths from (0, 0) to (n - 1, m - 1)
function numberOfPaths(m, n)
{
    // We have to calculate m+n-2 C n-1 here
    // which will be (m+n-2)! / (n-1)! (m-1)!
    var path = 1;
    for (var i = n; i < (m + n - 1); i++) {
        path *= i;
        path /= (i - n + 1);
    }
    return path;
}
 
// Function to return the total count of paths
// from (0, 0) to (n - 1, m - 1) that pass
// through at least one of the marked cells
function solve(maze)
{
 
    // Total count of paths - Total paths that do not
    // pass through any of the marked cell
    var ans = numberOfPaths(R, C) - countPaths(maze);
 
    // return answer
    return ans;
}
 
// Driver code
var maze = [ [ 0, 0, 0, 0 ],
                   [ 0, -1, 0, 0 ],
                   [ -1, 0, 0, 0 ],
                   [ 0, 0, 0, 0 ] ];
document.write( solve(maze));
 
// This code is contributed by rrrtnx.
</script>   

16

Complejidad temporal: O(R*C)
Espacio auxiliar: O(R*C)