Cuente la cantidad de formas de llegar al destino en un laberinto usando BFS

Dado un laberinto con obstáculos, cuente el número de caminos para llegar a la celda más a la derecha e inferior desde la celda más a la izquierda. Una celda en el laberinto dado tiene valor -1 si es un bloqueo o callejón sin salida, de lo contrario 0. 
Desde una celda dada, podemos movernos a las celdas (i+1, j) y (i, j+1) solamente.

Ejemplos: 

Entrada: mat[][] = { 
{1, 0, 0, 1}, 
{1, 1, 1, 1}, 
{1, 0, 1, 1}} 
Salida: 2

Entrada: mat[][] = { 
{1, 1, 1, 1}, 
{1, 0, 1, 1}, 
{0, 1, 1, 1}, 
{1, 1, 1, 1}} 
Salida : 4 
 

Enfoque: la idea es usar una cola y aplicar bfs y usar un recuento variable para almacenar la cantidad de rutas posibles. Haga un par de fila y columna e inserte (0, 0) en la cola. Ahora mantenga los pares emergentes de la cola, si el valor emergente es el final de la array, entonces incremente el conteo , de lo contrario verifique si la siguiente columna puede dar un movimiento válido o la siguiente fila puede dar un movimiento válido y de acuerdo con eso, inserte la fila correspondiente, par de columnas en la cola.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define m 4
#define n 3
 
// Function to return the number of valid
// paths in the given maze
int Maze(int matrix[n][m])
{
    queue<pair<int, int> > q;
 
    // Insert the starting point i.e.
    // (0, 0) in the queue
    q.push(make_pair(0, 0));
 
    // To store the count of possible paths
    int count = 0;
 
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
 
        // Increment the count of paths since
        // it is the destination
        if (p.first == n - 1 && p.second == m - 1)
            count++;
 
        // If moving to the next row is a valid move
        if (p.first + 1 < n
            && matrix[p.first + 1][p.second] == 1) {
            q.push(make_pair(p.first + 1, p.second));
        }
 
        // If moving to the next column is a valid move
        if (p.second + 1 < m
            && matrix[p.first][p.second + 1] == 1) {
            q.push(make_pair(p.first, p.second + 1));
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
    // Matrix to represent maze
    int matrix[n][m] = { { 1, 0, 0, 1 },
                         { 1, 1, 1, 1 },
                         { 1, 0, 1, 1 } };
 
    cout << Maze(matrix);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
class GFG
{
static int m = 4;
static int n = 3;
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to return the number of valid
// paths in the given maze
static int Maze(int matrix[][])
{
    Queue<pair> q = new LinkedList<>();
 
    // Insert the starting point i.e.
    // (0, 0) in the queue
    q.add(new pair(0, 0));
 
    // To store the count of possible paths
    int count = 0;
 
    while (!q.isEmpty())
    {
        pair p = q.peek();
        q.remove();
 
        // Increment the count of paths since
        // it is the destination
        if (p.first == n - 1 && p.second == m - 1)
            count++;
 
        // If moving to the next row is a valid move
        if (p.first + 1 < n &&
            matrix[p.first + 1][p.second] == 1)
        {
            q.add(new pair(p.first + 1, p.second));
        }
 
        // If moving to the next column is a valid move
        if (p.second + 1 < m &&
            matrix[p.first][p.second + 1] == 1)
        {
            q.add(new pair(p.first, p.second + 1));
        }
    }
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    // Matrix to represent maze
    int matrix[][] = {{ 1, 0, 0, 1 },
                      { 1, 1, 1, 1 },
                      { 1, 0, 1, 1 }};
 
    System.out.println(Maze(matrix));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
from collections import deque
m = 4
n = 3
 
# Function to return the number of valid
# paths in the given maze
def Maze(matrix):
    q = deque()
 
    # Insert the starting poi.e.
    # (0, 0) in the queue
    q.append((0, 0))
 
    # To store the count of possible paths
    count = 0
 
    while (len(q) > 0):
        p = q.popleft()
 
        # Increment the count of paths since
        # it is the destination
        if (p[0] == n - 1 and p[1] == m - 1):
            count += 1
 
        # If moving to the next row is a valid move
        if (p[0] + 1 < n and
            matrix[p[0] + 1][p[1]] == 1):
            q.append((p[0] + 1, p[1]))
 
        # If moving to the next column is a valid move
        if (p[1] + 1 < m and
            matrix[p[0]][p[1] + 1] == 1):
            q.append((p[0], p[1] + 1))
 
    return count
 
# Driver code
 
# Matrix to represent maze
matrix = [ [ 1, 0, 0, 1 ],
           [ 1, 1, 1, 1 ],
           [ 1, 0, 1, 1 ] ]
 
print(Maze(matrix))
     
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
static int m = 4;
static int n = 3;
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to return the number of valid
// paths in the given maze
static int Maze(int [,]matrix)
{
    Queue<pair> q = new Queue<pair>();
 
    // Insert the starting point i.e.
    // (0, 0) in the queue
    q.Enqueue(new pair(0, 0));
 
    // To store the count of possible paths
    int count = 0;
 
    while (q.Count != 0)
    {
        pair p = q.Peek();
        q.Dequeue();
 
        // Increment the count of paths since
        // it is the destination
        if (p.first == n - 1 && p.second == m - 1)
            count++;
 
        // If moving to the next row is a valid move
        if (p.first + 1 < n &&
            matrix[p.first + 1, p.second] == 1)
        {
            q.Enqueue(new pair(p.first + 1, p.second));
        }
 
        // If moving to the next column is a valid move
        if (p.second + 1 < m &&
            matrix[p.first, p.second + 1] == 1)
        {
            q.Enqueue(new pair(p.first, p.second + 1));
        }
    }
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    // Matrix to represent maze
    int [,]matrix = {{ 1, 0, 0, 1 },
                     { 1, 1, 1, 1 },
                     { 1, 0, 1, 1 }};
 
    Console.WriteLine(Maze(matrix));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
var m = 4;
var n = 3;
 
// Function to return the number of valid
// paths in the given maze
function Maze(matrix)
{
    var q = [];
 
    // Insert the starting point i.e.
    // (0, 0) in the queue
    q.push([0, 0]);
 
    // To store the count of possible paths
    var count = 0;
 
    while (q.length != 0)
    {
        var p = q[0];
        q.shift();
 
        // Increment the count of paths since
        // it is the destination
        if (p[0] == n - 1 && p[1] == m - 1)
            count++;
 
        // If moving to the next row is a valid move
        if (p[0] + 1 < n &&
            matrix[p[0] + 1][p[1]] == 1)
        {
            q.push([p[0] + 1, p[1]]);
        }
 
        // If moving to the next column is a valid move
        if (p[1] + 1 < m &&
            matrix[p[0]][p[1] + 1] == 1)
        {
            q.push([p[0], p[1] + 1]);
        }
    }
    return count;
}
 
// Driver code
 
// Matrix to represent maze
var matrix = [ [ 1, 0, 0, 1 ],
               [ 1, 1, 1, 1 ],
               [ 1, 0, 1, 1 ] ];
                
document.write( Maze(matrix));
 
// This code is contributed by rutvik_56
 
</script>

2

Complejidad Temporal: O(N * M). 
Espacio Auxiliar : O(N * M).