Minimice los giros necesarios para hacer que todos los caminos más cortos desde la parte superior izquierda hasta la parte inferior derecha de una array binaria sean iguales a S

Dada una array binaria mat[][] que tiene dimensiones N * M y una string binaria S de longitud N + M – 1 , la tarea es encontrar el número mínimo de vueltas requeridas para hacer todos los caminos más cortos desde la celda superior izquierda hasta la celda inferior derecha igual a la string dada S .

Ejemplos:

Entrada: mat[][] = [[1, 0, 1, 1], [1, 1, 1, 0]], S = “10010”
Salida: 3 
Explicación: 
Paso 1: [[1, 0, 1 , 1], [ 1 , 1, 1, 0]] -> [[1, 0, 1, 1], [ 0 , 1, 1, 0]] 
Paso 2: [[1, 0, 1 , 1] , [0, 1, 1, 0]] -> [[1, 0, 0, 1], [0, 1, 1, 0]] 
Paso 3: [[1, 0, 0, 1], [0 , 1 , 1, 0]] -> [[1, 0, 0, 1], [0, 0 , 1, 0]] 
Una vez realizados los pasos anteriores, cada ruta más corta desde la parte superior izquierda hasta la parte inferior derecha celda son iguales a S. 
Por lo tanto, el conteo requerido es 3.

Entrada: mat[][] =[[1, 0, 0, 1, 0]], S = “01101”
Salida: 5

Enfoque ingenuo: el enfoque más simple es generar recursivamente todos los cambios posibles en cada celda de la array dada y verificar qué combinación de los cambios mínimos genera la array que satisface la condición requerida. 
Complejidad de Tiempo: O(2 ^{N * M} )
Espacio Auxiliar: O(N * M)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es atravesar la array y observar que si (i, j) es el índice actual de la array dada, esta posición estará en la string de ruta más corta en el índice (i + j ) donde, i ∈ [0, N-1] y j ∈ [0, M-1] . 
Siga los pasos a continuación para resolver el problema:

1. Inicializar el contador como 0 .
2. Recorra cada posición de la array arr[][] .
3. Si la posición actual en la array dada es (i, j) , entonces, esta posición está en la string de ruta más corta en (i + j) ^th index.
4. En cada posición, compare arr[i][j] y S[i + j] . Si se encuentra igual, continúe con la siguiente posición. De lo contrario, aumente la cuenta en 1 .
5. Una vez realizados los pasos anteriores para toda la array, imprima el valor de conteo como el mínimo de volteos requerido.

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 count the minimum
// number of flips required
int minFlips(vector<vector<int> >& mat,
             string s)
{
    // Dimensions of matrix
    int N = mat.size();
    int M = mat[0].size();
 
    // Stores the count the flips
    int count = 0;
 
    for (int i = 0; i < N; i++) {
 
        for (int j = 0; j < M; j++) {
 
            // Check if element is same
            // or not
            if (mat[i][j]
                != s[i + j] - '0') {
                count++;
            }
        }
    }
 
    // Return the final count
    return count;
}
 
// Driver Code
int main()
{
    // Given Matrix
    vector<vector<int> > mat
        = { { 1, 0, 1 },
            { 0, 1, 1 },
            { 0, 0, 0 } };
 
    // Given path as a string
    string s = "10001";
 
    // Function Call
    cout << minFlips(mat, s);
 
    return 0;
}

// Java program for the above approach
class GFG {
 
    // Function to count the minimum
    // number of flips required
    static int minFlips(int mat[][],
                        String s)
    {
        // Dimensions of matrix
        int N = mat.length;
        int M = mat[0].length;
 
        // Stores the count the flips
        int count = 0;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                // Check if element is same
                // or not
                if (mat[i][j] !=
                    s.charAt(i + j) - '0')
                {
                    count++;
                }
            }
        }
 
        // Return the final count
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Matrix
        int mat[][] = {{1, 0, 1},
                       {0, 1, 1}, {0, 0, 0}};
 
        // Given path as a string
        String s = "10001";
 
        // Function Call
        System.out.print(minFlips(mat, s));
    }
}
 
// This code is contributed by Chitranayal

# Python3 program for the above approach
 
# Function to count the minimum
# number of flips required
def minFlips(mat, s):
 
    # Dimensions of matrix
    N = len(mat)
    M = len(mat[0])
 
    # Stores the count the flips
    count = 0
 
    for i in range(N):
        for j in range(M):
 
            # Check if element is same
            # or not
            if(mat[i][j] != ord(s[i + j]) -
                            ord('0')):
                count += 1
 
    # Return the final count
    return count
 
# Driver Code
 
# Given Matrix
mat = [ [ 1, 0, 1 ],
        [ 0, 1, 1 ],
        [ 0, 0, 0 ] ]
 
# Given path as a string
s = "10001"
 
# Function call
print(minFlips(mat, s))
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the minimum
// number of flips required
static int minFlips(int [,]mat,
                    String s)
{
     
    // Dimensions of matrix
    int N = mat.GetLength(0);
    int M = mat.GetLength(1);
 
    // Stores the count the flips
    int count = 0;
 
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
             
            // Check if element is same
            // or not
            if (mat[i, j] !=
                  s[i + j] - '0')
            {
                count++;
            }
        }
    }
 
    // Return the readonly count
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given Matrix
    int [,]mat = { { 1, 0, 1 },
                   { 0, 1, 1 },
                   { 0, 0, 0 } };
 
    // Given path as a string
    String s = "10001";
 
    // Function call
    Console.Write(minFlips(mat, s));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// javascript program for the
// above approach
 
    // Function to count the minimum
    // number of flips required
    function minFlips(mat, s)
    {
        // Dimensions of matrix
        let N = mat.length;
        let M = mat[0].length;
   
        // Stores the count the flips
        let count = 0;
   
        for (let i = 0; i < N; i++)
        {
            for (let j = 0; j < M; j++)
            {
                // Check if element is same
                // or not
                if (mat[i][j] !=
                    s[(i + j)] - '0')
                {
                    count++;
                }
            }
        }
   
        // Return the final count
        return count;
    }
  
// Driver Code
 
     // Given Matrix
        let mat = [[ 1, 0, 1],
                       [0, 1, 1], [0, 0, 0]];
   
        // Given path as a string
        let s = "10001";
   
        // Function Call
        document.write(minFlips(mat, s));
 
// This code is contributed by trget_2.
</script>

4

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)