Se requiere un número mínimo de vueltas para que se pueda llegar a la última celda de la array desde cualquier otra celda

Dada una array arr[][] de dimensiones N * M donde cada celda consta de los caracteres ‘R’ o ‘D’ excepto la celda arr[N][M] que contiene ‘F’ . ‘R’ y ‘D’ indican que el jugador puede moverse hacia la derecha y hacia abajo, respectivamente, desde la celda actual. La tarea es encontrar el número mínimo de caracteres necesarios para pasar de ‘R’ a ‘D’ o de ‘D’ a ‘R’ de modo que sea posible llegar a la celda final, es decir, arr[N][M] desde cada celda

Ejemplos:

Entrada: N = 2, M = 3, arr[][] = {{D, D, R}, {R, R, F}}
Salida: 1
Explicación: Después de cambiar la dirección de (1, 3) a ‘ D’, cada celda puede llegar al punto final.

Entrada: N = 1, M = 3, arr[1][3] = {{D, D, F}}
Salida: 2

Planteamiento: El problema se puede resolver observando que cada celda puede llegar al punto final después de cambiar las siguientes celdas:

• Cambie todas las ‘D’ a ‘R’ en la última fila.
• Cambie todas las ‘R’ por ‘D’ en la última columna.

Siga los pasos a continuación para resolver el problema:

1. Inicializa una variable, digamos ans , para almacenar el número mínimo de lanzamientos.
2. Recorra de i = 0 a N – 1 y cuente el número de celdas arr[i][M-1] que contiene ‘R’ .
3. Recorra desde i = 0 hasta M – 1 y cuente el número de celdas arr[N – 1][i] que contiene ‘D’ .
4. Imprima la suma de los dos conteos obtenidos en el paso anterior como la respuesta requerida.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum
// number of flips required
int countChanges(vector<vector<char> > mat)
{
    // Dimensions of mat[][]
    int n = mat.size();
    int m = mat[0].size();
 
    // Initialize answer
    int ans = 0;
 
    // Count all 'D's in the last row
    for (int j = 0; j < m - 1; j++) {
        if (mat[n - 1][j] != 'R')
            ans++;
    }
 
    // Count all 'R's in the last column
    for (int i = 0; i < n - 1; i++) {
        if (mat[i][m - 1] != 'D')
            ans++;
    }
 
    // Print answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given matrix
    vector<vector<char> > arr = { { 'R', 'R', 'R', 'D' },
                                  { 'D', 'D', 'D', 'R' },
                                  { 'R', 'D', 'R', 'F' } };
 
    // Function call
    int cnt = countChanges(arr);
 
    // Print answer
    cout << cnt << endl;
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to calculate the minimum
// number of flips required    
public static int countChanges(char mat[][])
{
     
    // Dimensions of mat[][]
    int n = mat.length;
    int m = mat[0].length;
 
    // Initialize answer
    int ans = 0;
 
    // Count all 'D's in the last row
    for(int j = 0; j < m - 1; j++)
    {
        if (mat[n - 1][j] != 'R')
            ans++;
    }
 
    // Count all 'R's in the last column
    for(int i = 0; i < n - 1; i++)
    {
        if (mat[i][m - 1] != 'D')
            ans++;
    }
     
    // Print answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    char arr[][] = { { 'R', 'R', 'R', 'D' },
                     { 'D', 'D', 'D', 'R' },
                     { 'R', 'D', 'R', 'F' } };
 
    // Function call
    int cnt = countChanges(arr);
 
    // Print answer
    System.out.println(cnt);
}
}
 
// This code is contributed by Manu Pathria

# Python3 program for the above approach
  
# Function to calculate the minimum
# number of flips required
def countChanges(mat):
     
    # Dimensions of mat[][]
    n = len(mat)
    m = len(mat[0])
  
    # Initialize answer
    ans = 0
  
    # Count all 'D's in the last row
    for j in range(m - 1):
        if (mat[n - 1][j] != 'R'):
            ans += 1
             
    # Count all 'R's in the last column
    for i in range(n - 1):
        if (mat[i][m - 1] != 'D'):
            ans += 1
 
    # Print answer
    return ans
 
# Driver Code
 
# Given matrix
arr = [ [ 'R', 'R', 'R', 'D' ] ,
        [ 'D', 'D', 'D', 'R' ],
        [ 'R', 'D', 'R', 'F' ] ]
  
# Function call
cnt = countChanges(arr)
  
# Print answer   
print(cnt)
 
# This code is contributed by susmitakundugoaldanga

// C# program for the above approach
using System;
 
class GFG{
     
// Function to calculate the minimum
// number of flips required    
public static int countChanges(char [,]mat)
{
     
    // Dimensions of [,]mat
    int n = mat.GetLength(0);
    int m = mat.GetLength(1);
     
    // Initialize answer
    int ans = 0;
     
    // Count all 'D's in the last row
    for(int j = 0; j < m - 1; j++)
    {
        if (mat[n - 1,j] != 'R')
            ans++;
    }
 
    // Count all 'R's in the last column
    for(int i = 0; i < n - 1; i++)
    {
        if (mat[i,m - 1] != 'D')
            ans++;
    }
     
    // Print answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    char [,]arr = { { 'R', 'R', 'R', 'D' },
                    { 'D', 'D', 'D', 'R' },
                    { 'R', 'D', 'R', 'F' } };
 
    // Function call
    int cnt = countChanges(arr);
 
    // Print answer
    Console.WriteLine(cnt);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program for the above approach
 
// Function to calculate the minimum
// number of flips required   
function countChanges(mat)
{
     
    // Dimensions of mat[][]
    let n = mat.length;
    let m = mat[0].length;
  
    // Initialize answer
    let ans = 0;
  
    // Count all 'D's in the last row
    for(let j = 0; j < m - 1; j++)
    {
        if (mat[n - 1][j] != 'R')
            ans++;
    }
  
    // Count all 'R's in the last column
    for(let i = 0; i < n - 1; i++)
    {
        if (mat[i][m - 1] != 'D')
            ans++;
    }
      
    // Print let answer
    return ans;
}
 
// Driver code
let arr = [ [ 'R', 'R', 'R', 'D' ],
            [ 'D', 'D', 'D', 'R' ],
            [ 'R', 'D', 'R', 'F' ] ];
 
// Function call
let cnt = countChanges(arr);
 
// Print let answer
document.write(cnt);
 
// This code is contributed by code_hunt
  
</script>

2

Complejidad temporal: O(N+M), donde N y M son dimensiones de la array.
Espacio Auxiliar: O(1) , ya que no hay espacio extra involucrado.