Verifique la posible ruta en la array 2D

Dada una array 2D (mxn). La tarea es verificar si hay algún camino desde la parte superior izquierda hasta la parte inferior derecha. En la array, -1 se considera como bloqueo (no puede atravesar esta celda) y 0 se considera celda de ruta (puede atravesarla).

Nota: la celda superior izquierda siempre contiene 0

Ejemplos: 

Entrada: array[][] = {{ 0, 0, 0, -1, 0}, 
{-1, 0, 0, -1, -1}, 
{ 0, 0, 0, -1, 0}, 
{-1, 0, 0, 0, 0}, 
{ 0, 0, -1, 0, 0}} 
Salida: Sí 
Explicación: 
 

Las celdas rojas están bloqueadas, las celdas blancas indican el camino y las celdas verdes no son celdas bloqueadas.

Entrada: array[][] = {{ 0, 0, 0, -1, 0}, 
{-1, 0, 0, -1, -1}, 
{ 0, 0, 0, -1, 0}, 
{-1, 0, -1, 0, 0}, 
{ 0, 0, -1, 0, 0}} 
Salida: No 
Explicación: No existe una ruta de principio a fin. 
 

Las celdas rojas están bloqueadas, las celdas blancas indican el camino y las celdas verdes no son celdas bloqueadas. 

Método 1

• Enfoque: la solución es realizar BFS o DFS para encontrar si hay una ruta o no. No es necesario crear el gráfico para realizar el bfs, pero la propia array se utilizará como gráfico. Comience el recorrido desde la esquina superior derecha y si hay una forma de llegar a la esquina inferior derecha, entonces hay un camino.
• Algoritmo: 
  1. Cree una cola que almacene pares (i,j) e inserte el (0,0) en la cola.
  2. Ejecute un bucle hasta que la cola esté vacía.
  3. En cada iteración, quite la cola de la cola (a,b) , si el elemento frontal es el destino (fila-1, columna-1), devuelva 1, es decir, hay una ruta y cambie el valor de mat[a][b ] a -1, es decir, visitado.
  4. De lo contrario, inserte los índices adyacentes donde el valor de la array [i] [j] no es -1.
• Implementación:

// C++ program to find if there is path
// from top left to right bottom
#include <bits/stdc++.h>
using namespace std;
 
#define row 5
#define col 5
 
// to find the path from
// top left to bottom right
bool isPath(int arr[row][col])
{
    // directions
    int dir[4][2]
        = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
    // queue
    queue<pair<int, int> > q;
 
    // insert the top right corner.
    q.push(make_pair(0, 0));
 
    // until queue is empty
    while (q.size() > 0) {
        pair<int, int> p = q.front();
        q.pop();
 
        // mark as visited
        arr[p.first][p.second] = -1;
 
        // destination is reached.
        if (p == make_pair(row - 1, col - 1))
            return true;
 
        // check all four directions
        for (int i = 0; i < 4; i++) {
            // using the direction array
            int a = p.first + dir[i][0];
            int b = p.second + dir[i][1];
 
            // not blocked and valid
            if (arr[a][b] != -1 && a >= 0 && b >= 0
                && a < row && b < col) {
                q.push(make_pair(a, b));
            }
        }
    }
    return false;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[row][col] = { { 0, 0, 0, -1, 0 },
                          { -1, 0, 0, -1, -1 },
                          { 0, 0, 0, -1, 0 },
                          { -1, 0, 0, 0, 0 },
                          { 0, 0, -1, 0, 0 } };
 
    // path from arr[0][0] to arr[row][col]
    if (isPath(arr))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program to find if there is path
// from top left to right bottom
import java.io.*;
import java.util.*;
 
class pair {
    int Item1, Item2;
    pair(int f, int s)
    {
        Item1 = f;
        Item2 = s;
    }
}
 
class GFG {
 
    static int row = 5;
    static int col = 5;
 
    // To find the path from
    // top left to bottom right
    static boolean isPath(int[][] arr)
    {
 
        // Directions
        int[][] dir
            = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
        // Queue
        Queue<pair> q = new LinkedList<>();
 
        // Insert the top right corner.
        q.add(new pair(0, 0));
 
        // Until queue is empty
        while (q.size() > 0) {
            pair p = (q.peek());
            q.remove();
 
            // Mark as visited
            arr[p.Item1][p.Item2] = -1;
 
            // Destination is reached.
            if (p.Item1 == row - 1 && p.Item2 == col - 1)
                return true;
 
            // Check all four directions
            for (int i = 0; i < 4; i++) {
 
                // Using the direction array
                int a = p.Item1 + dir[i][0];
                int b = p.Item2 + dir[i][1];
 
                // Not blocked and valid
                if (a >= 0 && b >= 0 && a < row && b < col
                    && arr[a][b] != -1) {
                    if (a == row - 1 && b == col - 1)
                        return true;
 
                    q.add(new pair(a, b));
                }
            }
        }
        return false;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array
        int[][] arr = { { 0, 0, 0, -1, 0 },
                        { -1, 0, 0, -1, -1 },
                        { 0, 0, 0, -1, 0 },
                        { -1, 0, 0, 0, 0 },
                        { 0, 0, -1, 0, 0 } };
 
        // Path from arr[0][0] to arr[row][col]
        if (isPath(arr))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by avanitrachhadiya2155

# Python3 program to find if there is path
# from top left to right bottom
row = 5
col = 5
 
# to find the path from
# top left to bottom right
def isPath(arr) :
 
    # directions
    Dir = [ [0, 1], [0, -1], [1, 0], [-1, 0]]
     
    # queue
    q = []
     
    # insert the top right corner.
    q.append((0, 0))
     
    # until queue is empty
    while(len(q) > 0) :
        p = q[0]
        q.pop(0)
         
        # mark as visited
        arr[p[0]][p[1]] = -1
         
        # destination is reached.
        if(p == (row - 1, col - 1)) :
            return True
             
        # check all four directions
        for i in range(4) :
         
            # using the direction array
            a = p[0] + Dir[i][0]
            b = p[1] + Dir[i][1]
             
            # not blocked and valid
            if(a >= 0 and b >= 0 and a < row and b < col and arr[a][b] != -1) :           
                q.append((a, b))
    return False
   
# Given array
arr = [[ 0, 0, 0, -1, 0 ],
          [ -1, 0, 0, -1, -1],
          [ 0, 0, 0, -1, 0 ],
          [ -1, 0, 0, 0, 0 ],
          [ 0, 0, -1, 0, 0 ] ]
 
# path from arr[0][0] to arr[row][col]
if (isPath(arr)) :
    print("Yes")
else :
    print("No")
 
    # This code is contributed by divyesh072019

<script>
 
// JavaScript program to find if there is path 
// from top left to right bottom
 
var row = 5;
var col = 5;
 
// To find the path from
// top left to bottom right
function isPath(arr)
{
     
    // Directions
    var dir = [ [ 0, 1 ], [ 0, -1 ],
                   [ 1, 0 ], [ -1, 0 ] ];
       
    // Queue
    var q = [];
     
    // Insert the top right corner.
    q.push([0, 0]);
       
    // Until queue is empty
    while (q.length > 0)
    {
        var p = q[0];
        q.shift();
           
        // Mark as visited
        arr[p[0]][p[1]] = -1;
           
        // Destination is reached. 
        if (p[0]==row-1 && p[1]==col-1)
            return true;
               
        // Check all four directions
        for(var i = 0; i < 4; i++)
        {
             
            // Using the direction array
            var a = p[0] + dir[i][0];
            var b = p[1] + dir[i][1];
               
            // Not blocked and valid
            if (a >= 0 && b >= 0 &&
               a < row && b < col &&
                  arr[a][b] != -1)
            {
                if (a==row - 1 && b==col - 1)
                    return true;
                q.push([a,b]);
            }
        }
    }
    return false;
}
 
// Driver Code
// Given array
var arr = [[ 0, 0, 0, -1, 0 ],
          [ -1, 0, 0, -1, -1],
          [ 0, 0, 0, -1, 0 ],
          [ -1, 0, 0, 0, 0 ],
          [ 0, 0, -1, 0, 0 ] ];
 
// Path from arr[0][0] to arr[row][col]
if (isPath(arr))
    document.write("Yes");
else
    document.write("No");
 
 
</script>

Producción: 

No

• Análisis de Complejidad: 
  • Complejidad Temporal: O(R*C). 
    Cada elemento de la array se puede insertar una vez en la cola, por lo que la Complejidad del tiempo es O(R*C).
  • Complejidad espacial: O(R*C). 
    Para almacenar todos los elementos en una cola se necesita un espacio O(R*C).

Método 2 

• Enfoque: el único problema con la solución anterior es que utiliza espacio adicional. Este enfoque eliminará la necesidad de espacio adicional. La idea básica es muy similar. Este algoritmo también realizará BFS, pero la necesidad de espacio adicional se eliminará marcando la array. Entonces, primero ejecute un bucle y verifique qué elementos de la primera columna y la primera fila son accesibles desde 0,0 usando solo la primera fila y la primera columna. márquelos como 1. Ahora recorra la array desde el principio hasta el final en forma de fila en el índice creciente de filas y columnas. Si la celda no está bloqueada, verifique que cualquiera de sus celdas adyacentes esté marcada con 1 o no. Si marcó 1, marque la celda 1.
• Algoritmo: 
  1. Marque la celda 0,0 como 1.
  2. Ejecute un ciclo desde 0 hasta la longitud de la fila y si la celda de arriba está marcada como 1 y la celda actual no está bloqueada, marque la celda actual como 1.
  3. Ejecute un ciclo desde 0 hasta la longitud de la columna y si la celda izquierda está marcada como 1 y la celda actual no está bloqueada, marque la celda actual como 1.
  4. Atraviese la array desde el principio hasta el final en filas aumentando el índice de filas y columnas.
  5. Si la celda no está bloqueada, verifique que cualquiera de sus celdas adyacentes (marque solo la celda de arriba y la celda de la izquierda). está marcado con 1 o no. Si marcó 1, marque la celda 1.
  6. Si la celda (fila-1, columna-1) está marcada como 1, devuelve verdadero; de lo contrario, devuelve falso.
• Implementación:

// C++ program to find if there is path
// from top left to right bottom
#include <iostream>
using namespace std;
 
#define row 5
#define col 5
 
// to find the path from
// top left to bottom right
bool isPath(int arr[row][col])
{
    // set arr[0][0] = 1
    arr[0][0] = 1;
 
    // Mark reachable (from top left) nodes
    // in first row and first column.
    for (int i = 1; i < row; i++)
        if (arr[i][0] != -1)
            arr[i][0] = arr[i - 1][0];  
 
    for (int j = 1; j < col; j++)
        if (arr[0][j] != -1)
            arr[0][j] = arr[0][j - 1];   
 
    // Mark reachable nodes in remaining
    // matrix.
    for (int i = 1; i < row; i++)
        for (int j = 1; j < col; j++)
          if (arr[i][j] != -1)
              arr[i][j] = max(arr[i][j - 1],
                            arr[i - 1][j]);      
     
    // return yes if right bottom
    // index is 1
    return (arr[row - 1][col - 1] == 1);
}
 
// Driver Code
int main()
{
    // Given array
    int arr[row][col] = { { 0, 0, 0, -1, 0 },
                          { -1, 0, 0, -1, -1 },
                          { 0, 0, 0, -1, 0 },
                          { -1, 0, -1, 0, -1 },
                          { 0, 0, -1, 0, 0 } };
 
    // path from arr[0][0] to arr[row][col]
    if (isPath(arr))
      cout << "Yes";
    else
      cout << "No";
 
return 0;
}

// Java program to find if there is path
// from top left to right bottom
class GFG
{
    // to find the path from
    // top left to bottom right
    static boolean isPath(int arr[][])
    {
        // set arr[0][0] = 1
        arr[0][0] = 1;
 
        // Mark reachable (from top left) nodes
        // in first row and first column.
        for (int i = 1; i < 5; i++)
            if (arr[0][i] != -1)
                arr[0][i] = arr[0][i - 1];
        for (int j = 1; j < 5; j++)
            if (arr[j][0] != -1)
                arr[j][0] = arr[j - 1][0];
 
        // Mark reachable nodes in
        //  remaining matrix.
        for (int i = 1; i < 5; i++)
            for (int j = 1; j < 5; j++)
                if (arr[i][j] != -1)
                    arr[i][j] = Math.max(arr[i][j - 1],
                                        arr[i - 1][j]);
 
        // return yes if right
        // bottom index is 1
        return (arr[5 - 1][5 - 1] == 1);
    }
      
    //Driver code
    public static void main(String[] args)
    {
        // Given array
        int arr[][] = { { 0, 0, 0, -1, 0 },
                        { -1, 0, 0, -1, -1 },
                        { 0, 0, 0, -1, 0 },
                        { -1, 0, -1, 0, -1 },
                        { 0, 0, -1, 0, 0 } };
 
        // path from arr[0][0]
        // to arr[row][col]
        if (isPath(arr))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
// This code is contributed
// by prerna saini

# Python3 program to find if there
# is path from top left to right bottom
row = 5
col = 5
 
# to find the path from
# top left to bottom right
def isPath(arr):
     
    # set arr[0][0] = 1
    arr[0][0] = 1
 
    # Mark reachable (from top left)
    # nodes in first row and first column.
    for i in range(1, row):
        if (arr[i][0] != -1):
            arr[i][0] = arr[i-1][0]
 
    for j in range(1, col):
        if (arr[0][j] != -1):
            arr[0][j] = arr[0][j-1]
             
    # Mark reachable nodes in
    # remaining matrix.
    for i in range(1, row):
        for j in range(1, col):
            if (arr[i][j] != -1):
                arr[i][j] = max(arr[i][j - 1],
                                arr[i - 1][j])
                                 
    # return yes if right
    # bottom index is 1
    return (arr[row - 1][col - 1] == 1)
 
# Driver Code
 
# Given array
arr = [[ 0, 0, 0, -1, 0 ],
       [-1, 0, 0, -1, -1],
       [ 0, 0, 0, -1, 0 ],
       [-1, 0, -1, 0, -1],
       [ 0, 0, -1, 0, 0 ]]
 
# path from arr[0][0] to arr[row][col]
if (isPath(arr)):
    print("Yes")
else:
    print("No")
 
# This code is contributed
# by sahilshelangia

// C# program to find if there is path
// from top left to right bottom
using System;
 
class GFG
{
    // to find the path from
    // top left to bottom right
    static bool isPath(int [,]arr)
    {
        // set arr[0][0] = 1
        arr[0, 0] = 1;
 
        // Mark reachable (from top left) nodes
        // in first row and first column.
        for (int i = 1; i < 5; i++)
            if (arr[i, 0] != -1)
                arr[i, 0] = arr[i - 1, 0];
        for (int j = 1; j < 5; j++)
            if (arr[0,j] != -1)
                arr[0,j] = arr[0, j - 1];
 
        // Mark reachable nodes in
        // remaining matrix.
        for (int i = 1; i < 5; i++)
            for (int j = 1; j < 5; j++)
                if (arr[i, j] != -1)
                    arr[i, j] = Math.Max(arr[i, j - 1],
                                        arr[i - 1, j]);
 
        // return yes if right
        // bottom index is 1
        return (arr[5 - 1, 5 - 1] == 1);
    }
     
    //Driver code
    public static void Main()
    {
        // Given array
        int [,]arr = { { 0, 0, 0, -1, 0 },
                        { -1, 0, 0, -1, -1 },
                        { 0, 0, 0, -1, 0 },
                        { -1, 0, -1, 0, -1 },
                        { 0, 0, -1, 0, 0 } };
 
        // path from arr[0][0]
        // to arr[row][col]
        if (isPath(arr))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed
// by vt_m

<?php
// PHP program to find if
// there is path from top
// left to right bottom
$row = 5;
$col = 5;
 
// to find the path from
// top left to bottom right
function isPath($arr)
{
    global $row, $col;
     
    $arr[0][0] = 1;
 
    // Mark reachable (from
    // top left) nodes in
    // first row and first column.
    for ($i = 1; $i < $row; $i++)
        if ($arr[$i][0] != -1)
            $arr[$i][0] = $arr[$i - 1][0];
 
    for ($j = 1; $j < $col; $j++)
        if ($arr[0][$j] != -1)
            $arr[0][$j] = $arr[0][$j - 1];
 
    // Mark reachable nodes
    // in remaining matrix.
    for ($i = 1; $i < $row; $i++)
        for ($j = 1; $j < $col; $j++)
        if ($arr[$i][$j] != -1)
            $arr[$i][$j] = max($arr[$i][$j - 1],
                               $arr[$i - 1][$j]);
     
    // return yes if right
    // bottom index is 1
    return ($arr[$row - 1][$col - 1] == 1);
}
 
// Driver Code
 
// Given array
$arr = array(array(0, 0, 0, 1, 0),
             array(-1, 0, 0, -1, -1),
             array(0, 0, 0, -1, 0),
             array(-1, 0, -1, 0, -1),
             array(0, 0, -1, 0, 0));
 
// path from arr[0][0]
// to arr[row][col]
if (isPath($arr))
echo "Yes";
else
echo "No";
     
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript program to find if there is path
// from top left to right bottom
var arr = [[5], [5]]
// to find the path from
// top left to bottom right
function isPath(arr)
{
    // set arr[0][0] = 1
    arr[0][0] = 1;
  
    // Mark reachable (from top left) nodes
    // in first row and first column.
    for (var i = 1; i < 5; i++)
        if (arr[i][0] != -1)
            arr[i][0] = arr[i - 1][0];  
  
    for (var j = 1; j < 5; j++)
        if (arr[0][j] != -1)
            arr[0][j] = arr[0][j - 1];   
  
    // Mark reachable nodes in remaining
    // matrix.
    for (var i = 1; i < 5; i++)
        for (var j = 1; j < 5; j++)
          if (arr[i][j] != -1)
              arr[i][j] = Math.max(arr[i][j - 1],
                            arr[i - 1][j]);      
      
    // return yes if right bottom
    // index is 1
    return (arr[5 - 1][5 - 1] == 1);
}
  
// Driver Code
 
    // Given array
    var arr = [ [ 0, 0, 0, -1, 0 ],
                          [ -1, 0, 0, -1, -1 ],
                          [ 0, 0, 0, -1, 0 ],
                          [ -1, 0, -1, 0, -1 ],
                          [ 0, 0, -1, 0, 0 ] ];
  
    // path from arr[0][0] to arr[row][col]
    if (isPath(arr))
      document.write("Yes");
    else
      document.write("No");
  
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 

No

• Análisis de Complejidad: 
  • Complejidad Temporal: O(R*C). 
    Cada elemento de la array es atravesado, por lo que la Complejidad del tiempo es O(R*C).
  • Complejidad espacial: O(1). 
    No se necesita espacio adicional.