Verifique si existe una ruta desde el principio hasta el final de la celda en Matrix dada con obstáculos en la mayoría de los movimientos K

Dado un entero positivo K y una cuadrícula matricial de dimensiones N * M que consta de caracteres ‘.’ y ‘#’ , donde ‘.’ representa las celdas desbloqueadas y ‘#’ representa las celdas bloqueadas, la tarea es verificar si se puede llegar a la parte inferior derecha de la cuadrícula desde la celda superior izquierda de la array a través de celdas desbloqueadas en un máximo de K movimientos o no, de modo que se necesita un movimiento para moverse a su celda adyacente en la dirección derecha o hacia abajo.

Ejemplos:

Entrada: cuadrícula[][] = {{‘.’, ‘.’, ‘.’}, {‘#’, ‘.’, ‘.’}, {‘#’, ‘#’, ‘.’} }, K = 4
Salida: Sí
Explicación: Es posible llegar a la celda inferior derecha de la cuadrícula dada utilizando el siguiente conjunto de movimientos: derecha -> abajo -> derecha -> abajo. Por lo tanto, el número de movimientos requeridos es 4, que es el mínimo posible y es menor que K.

Entrada: cuadrícula[][] = {{‘.’, ‘.’, ‘.’, ‘.’}, {‘.’, ‘.’, ‘.’, ‘.’}, {‘#’, ‘#’, ‘#’, ‘#’}, {‘.’, ‘.’, ‘.’, ‘.’}}, K = 4
Salida: No
Explicación: No hay un conjunto posible de movimientos para alcanzar el celda inferior derecha de la celda superior izquierda de la array dada.

Enfoque: el problema dado se puede resolver con la ayuda de la programación dinámica mediante el uso de un enfoque de tabulación . Se puede resolver calculando previamente la cantidad mínima de movimientos necesarios para pasar de la celda superior izquierda a la celda inferior derecha utilizando un enfoque similar al que se analiza en este artículo. Se puede observar que si dp[i][j] representa el número mínimo de movimientos para llegar a la celda (i, j) desde (0, 0) , entonces la relación DP se puede formular de la siguiente manera:

dp[i][j] = min(dp[i][j], 1 + dp[i – 1][j], 1+ dp[i][j – 1]))

A partir de entonces, si el número mínimo de movimientos es como máximo K , imprima «Sí», de lo contrario imprima «No». 

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

// C++ implementation for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to check if it is possible
// to reach the bottom right of the grid
// from top left using atmost K moves
string canReach(vector<vector<char> >& grid, int K)
{
    int N = grid.size();
    int M = grid[0].size();
 
    // Stores the DP states
    vector<vector<long long> > dp(
        N, vector<long long>(M, INT_MAX));
     
      // if first cell or last cell is blocked then
    // not possible
    if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.')
      return "No";
   
    // Initial condition
    dp[0][0] = 0;
 
    // Initializing the DP table
    // in 1st row
    for (int i = 1; i < M; i++) {
        if (grid[0][i] == '.') {
            dp[0][i] = 1 + dp[0][i - 1];
        }
        else
            break;
    }
 
    // Initializing the DP table
    // in 1st column
    for (int i = 1; i < N; i++) {
        if (grid[i][0] == '.') {
            dp[i][0] = 1 + dp[i - 1][0];
        }
        else
            break;
    }
 
    // Iterate through the grid
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
 
            // If current position
            // is not an obstacle,
            // update the dp state
            if (grid[i][j] == '.') {
                dp[i][j] = min(
                    dp[i][j],
                    1 + min(dp[i - 1][j],
                            dp[i][j - 1]));
            }
        }
    }
 
    // Return answer
    return (dp[N - 1][M - 1] <= K
                ? "Yes"
                : "No");
}
 
// Driver Code
int main()
{
    vector<vector<char> > grid
        = { { '.', '.', '.' },
           { '#', '.', '.' },
           { '#', '#', '.' } };
   
    int K = 4;
    cout << canReach(grid, K);
 
    return 0;
}

// Java implementation for the above approach
//include "bits/stdJava.h"
import java.util.*;
 
class GFG
{
 
// Function to check if it is possible
// to reach the bottom right of the grid
// from top left using atmost K moves
static String canReach(char[][] grid, int K)
{
    int N = grid.length;
    int M = grid[0].length;
 
    // Stores the DP states
    int[][] dp = new int[N][M];
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++) {
            dp[i][j] = Integer.MAX_VALUE;
        }
    }
   
    // if first cell or last cell is blocked then
    // not possible
    if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.') return "No";
   
    // Initial condition
    dp[0][0] = 0;
 
    // Initializing the DP table
    // in 1st row
    for (int i = 1; i < M; i++) {
        if (grid[0][i] == '.') {
            dp[0][i] = 1 + dp[0][i - 1];
        }
        else
            break;
    }
 
    // Initializing the DP table
    // in 1st column
    for (int i = 1; i < N; i++) {
        if (grid[i][0] == '.') {
            dp[i][0] = 1 + dp[i - 1][0];
        }
        else
            break;
    }
 
    // Iterate through the grid
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
 
            // If current position
            // is not an obstacle,
            // update the dp state
            if (grid[i][j] == '.') {
                dp[i][j] = Math.min(
                    dp[i][j],
                    1 + Math.min(dp[i - 1][j],
                            dp[i][j - 1]));
            }
        }
    }
 
    // Return answer
    return (dp[N - 1][M - 1] <= K
                ? "Yes"
                : "No");
}
 
// Driver Code
public static void main(String[] args)
{
    char[][] grid
        = { { '.', '.', '.' },
           { '#', '.', '.' },
           { '#', '#', '.' } };
   
    int K = 4;
    System.out.print(canReach(grid, K));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation for the above approach
INT_MAX = 2147483647
 
# Function to check if it is possible
# to reach the bottom right of the grid
# from top left using atmost K moves
def canReach(grid, K):
     
    N = len(grid)
    M = len(grid[0])
 
    # Stores the DP states
    dp = [[INT_MAX for _ in range(M)]
                   for _ in range(N)]
     
    # if first cell or last cell is blocked then
    # not possible
    if(grid[0][0] != '.' or grid[N - 1][M - 1] != '.'):
      return("No")
   
    # Initial condition
    dp[0][0] = 0
 
    # Initializing the DP table
    # in 1st row
    for i in range(1, M):
        if (grid[0][i] == '.'):
            dp[0][i] = 1 + dp[0][i - 1]
        else:
            break
         
    # Initializing the DP table
    # in 1st column
    for i in range(1, N):
        if (grid[i][0] == '.'):
            dp[i][0] = 1 + dp[i - 1][0]
        else:
            break
 
    # Iterate through the grid
    for i in range(1, N):
        for j in range(1, M):
 
            # If current position
            # is not an obstacle,
            # update the dp state
            if (grid[i][j] == '.'):
                dp[i][j] = min(dp[i][j],
                       1 + min(dp[i - 1][j],
                               dp[i][j - 1]))
 
    # Return answer
    if dp[N - 1][M - 1] <= K:
        return("Yes")
    else:
        return("No")
 
# Driver Code
if __name__ == "__main__":
 
    grid = [ [ '.', '.', '.' ],
             [ '#', '.', '.' ],
             [ '#', '#', '.' ] ]
    K = 4
     
    print(canReach(grid, K))
 
# This code is contributed by rakeshsahni

// C# implementation for the above approach
//include "bits/stdJava.h"
using System;
 
class GFG
{
 
// Function to check if it is possible
// to reach the bottom right of the grid
// from top left using atmost K moves
static String canReach(char[,] grid, int K)
{
    int N = grid.GetLength(0);
    int M = grid.GetLength(1);
 
 
    // Stores the DP states
    int[,] dp = new int[N,M];
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++) {
            dp[i, j] = int.MaxValue;
        }
    }
     
    // if first cell or last cell is blocked then
    // not possible
    if(grid[0, 0] != '.' || grid[N - 1, M - 1] != '.') return "No";
   
    // Initial condition
    dp[0, 0] = 0;
 
    // Initializing the DP table
    // in 1st row
    for (int i = 1; i < M; i++) {
        if (grid[0, i] == '.') {
            dp[0, i] = 1 + dp[0, i - 1];
        }
        else
            break;
    }
 
    // Initializing the DP table
    // in 1st column
    for (int i = 1; i < N; i++) {
        if (grid[i, 0] == '.') {
            dp[i, 0] = 1 + dp[i - 1, 0];
        }
        else
            break;
    }
 
    // Iterate through the grid
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
 
            // If current position
            // is not an obstacle,
            // update the dp state
            if (grid[i, j] == '.') {
                dp[i, j] = Math.Min(
                    dp[i, j],
                    1 + Math.Min(dp[i - 1, j],
                            dp[i, j - 1]));
            }
        }
    }
 
    // Return answer
    return (dp[N - 1, M - 1] <= K
                ? "Yes"
                : "No");
}
 
// Driver Code
public static void Main()
{
    char[,] grid
        = { { '.', '.', '.' },
            { '/', '.', '.' },
            { '/', '/', '.' } };
    int K = 4;
    Console.Write(canReach(grid, K));
}
}
 
// This code is contributed by Saurabh jaiswal

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Function to check if it is possible
       // to reach the bottom right of the grid
       // from top left using atmost K moves
       function canReach(grid, K) {
           let N = grid.length;
           let M = grid[0].length;
 
           // Stores the DP states
           let dp = new Array(N);
           for (let i = 0; i < dp.length; i++) {
               dp[i] = new Array(M).fill(Number.MAX_VALUE);
           }
            
           // if first cell or last cell is blocked then
           // not possible
           if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.') return "No";
    
           // Initial condition
           dp[0][0] = 0;
 
           // Initializing the DP table
           // in 1st row
           for (let i = 1; i < M; i++) {
               if (grid[0][i] == '.') {
                   dp[0][i] = 1 + dp[0][i - 1];
               }
               else
                   break;
           }
 
           // Initializing the DP table
           // in 1st column
           for (let i = 1; i < N; i++) {
               if (grid[i][0] == '.') {
                   dp[i][0] = 1 + dp[i - 1][0];
               }
               else
                   break;
           }
 
           // Iterate through the grid
           for (let i = 1; i < N; i++) {
               for (let j = 1; j < M; j++) {
 
                   // If current position
                   // is not an obstacle,
                   // update the dp state
                   if (grid[i][j] == '.') {
                       dp[i][j] = Math.min(
                           dp[i][j],
                           1 + Math.min(dp[i - 1][j],
                               dp[i][j - 1]));
                   }
               }
           }
 
           // Return answer
           return (dp[N - 1][M - 1] <= K
               ? "Yes"
               : "No");
       }
 
       // Driver Code
       let grid
           = [['.', '.', '.'],
           ['#', '.', '.'],
           ['#', '#', '.']];
       let K = 4;
       document.write(canReach(grid, K));
 
   // This code is contributed by Potta Lokesh
   </script>

Yes

Complejidad de tiempo : O (N * M), ya que estamos usando bucles anidados para atravesar N * M veces.

Espacio auxiliar : O (N * M), ya que estamos usando espacio adicional para la array dp.