Минимум ячеек, которые нужно перевернуть, чтобы получить подматрицу 2 * 2 с равными элементами

Опубликовано: 29 Декабря, 2021

Учитывая матрицу размера M * N , задача состоит в том, чтобы найти минимальное количество ячеек, которые должны быть перевернуты, чтобы существовала хотя бы подматрица размера 2 * 2 со всеми равными элементами.
Примеры:

Input: mat[] = {“00000”, “10111”, “00000”, “11111”}
Output: 1
One of the possible submatrix could be {{0, 0}, {1, 0}}
where only a single element has to be flipped.
Input: mat[] = {“0101”, “0101”, “0101”}
Output: 3

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: для каждой подматрицы размером 2 * 2 подсчитайте количество нулей и количество единиц в ней, и минимум из этих двух будет количеством переворотов, необходимых для получения матрицы со всеми равными элементами. Минимум этого значения для всех подматриц является требуемым ответом.
Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to return the minimum flips
 // required such that the submatrix from
 // mat[i][j] to mat[i + 1][j + 1]
 // contains all equal elements
 int minFlipsSub(string mat[], int i, int j)
 {
    int cnt0 = 0, cnt1 = 0; 
    if (mat[i][j] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i][j + 1] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1][j] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1][j + 1] == '1' )
        cnt1++;
    else
        cnt0++;
    return min(cnt0, cnt1);
 }
 // Function to return the minimum number
 // of slips required such that the matrix
 // contains at least a single submatrix
 // of size 2*2 with all equal elements
 int minFlips(string mat[], int r, int c)
 {
    // To store the result
    int res = INT_MAX; 
    // For every submatrix of size 2*2
    for ( int i = 0; i < r - 1; i++) {
        for ( int j = 0; j < c - 1; j++) { 
            // Update the count of flips required
            // for the current submatrix
            res = min(res, minFlipsSub(mat, i, j));
        }
    }
    return res;
 }
 // Driver code
 int main()
 {
    string mat[] = { "0101" , "0101" , "0101" };
    int r = sizeof (mat) / sizeof (string);
    int c = mat[0].length(); 
    cout << minFlips(mat, r, c);
    return 0;
 }

Джава

 // Java implementation of the approach
 class GFG
 {
 // Function to return the minimum flips
 // required such that the submatrix from
 // mat[i][j] to mat[i + 1][j + 1]
 // contains all equal elements
 static int minFlipsSub(String mat[], int i, int j)
 {
    int cnt0 = 0 , cnt1 = 0 ; 
    if (mat[i].charAt(j) == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i].charAt(j+ 1 ) == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1 ].charAt(j) == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1 ].charAt(j+ 1 ) == '1' )
        cnt1++;
    else
        cnt0++;
    return Math.min(cnt0, cnt1);
 }
 // Function to return the minimum number
 // of slips required such that the matrix
 // contains at least a single submatrix
 // of size 2*2 with all equal elements
 static int minFlips(String mat[], int r, int c)
 {
    // To store the result
    int res = Integer.MAX_VALUE; 
    // For every submatrix of size 2*2
    for ( int i = 0 ; i < r - 1 ; i++)
    {
        for ( int j = 0 ; j < c - 1 ; j++)
        {
            // Update the count of flips required
            // for the current submatrix
            res = Math.min(res, minFlipsSub(mat, i, j));
        }
    }
    return res;
 }
 // Driver code
 public static void main(String[] args)
 {
    String mat[] = { "0101" , "0101" , "0101" };
    int r = mat.length;
    int c = mat[ 0 ].length(); 
    System.out.print(minFlips(mat, r, c));
 }
 }
 // This code is contributed by 29AjayKumar

Python 3

 # Python 3 implementation of the approach
 import sys
 # Function to return the minimum flips
 # required such that the submatrix from
 # mat[i][j] to mat[i + 1][j + 1]
 # contains all equal elements
 def minFlipsSub(mat, i, j):
    cnt0 = 0
    cnt1 = 0 
    if (mat[i][j] = = '1' ):
        cnt1 + = 1
    else :
        cnt0 + = 1 
    if (mat[i][j + 1 ] = = '1' ):
        cnt1 + = 1
    else :
        cnt0 + = 1 
    if (mat[i + 1 ][j] = = '1' ):
        cnt1 + = 1
    else :
        cnt0 + = 1 
    if (mat[i + 1 ][j + 1 ] = = '1' ):
        cnt1 + = 1
    else :
        cnt0 + = 1 
    return min (cnt0, cnt1)
 # Function to return the minimum number
 # of slips required such that the matrix
 # contains at least a single submatrix
 # of size 2*2 with all equal elements
 def minFlips(mat, r, c):
    
    # To store the result
    res = sys.maxsize 
    # For every submatrix of size 2*2
    for i in range (r - 1 ):
        for j in range (c - 1 ):
            
            # Update the count of flips required
            # for the current submatrix
            res = min (res, minFlipsSub(mat, i, j)) 
    return res
 # Driver code
 if __name__ = = '__main__' :
    mat = [ "0101" , "0101" , "0101" ]
    r = len (mat)
    c = len (mat[ 0 ]) 
    print (minFlips(mat, r, c))
    
# This code is contributed by Surendra_Gangwar

C #

 // C# implementation of the approach
 using System;
 class GFG
 {
 // Function to return the minimum flips
 // required such that the submatrix from
 // mat[i,j] to mat[i + 1,j + 1]
 // contains all equal elements
 static int minFlipsSub(String []mat,
                       int i, int j)
 {
    int cnt0 = 0, cnt1 = 0; 
    if (mat[i][j] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i][j + 1] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1][j] == '1' )
        cnt1++;
    else
        cnt0++;
    if (mat[i + 1][j + 1] == '1' )
        cnt1++;
    else
        cnt0++;
    return Math.Min(cnt0, cnt1);
 }
 // Function to return the minimum number
 // of slips required such that the matrix
 // contains at least a single submatrix
 // of size 2*2 with all equal elements
 static int minFlips(String []mat,
                    int r, int c)
 {
    // To store the result
    int res = int .MaxValue; 
    // For every submatrix of size 2*2
    for ( int i = 0; i < r - 1; i++)
    {
        for ( int j = 0; j < c - 1; j++)
        {
            // Update the count of flips required
            // for the current submatrix
            res = Math.Min(res, minFlipsSub(mat, i, j));
        }
    }
    return res;
 }
 // Driver code
 public static void Main(String[] args)
 {
    String []mat = { "0101" , "0101" , "0101" };
    int r = mat.Length;
    int c = mat.GetLength(0); 
    Console.Write(minFlips(mat, r, c));
 }
 }
 // This code is contributed by 29AjayKumar

Javascript

 <script>
 // javascript implementation of the approach
 // Function to return the minimum flips
    // required such that the submatrix from
    // mat[i][j] to mat[i + 1][j + 1]
    // contains all equal elements
    function minFlipsSub( mat , i , j)
    {
        var cnt0 = 0, cnt1 = 0; 
        if (mat[i].charAt(j) == '1' )
            cnt1++;
        else
            cnt0++;
        if (mat[i].charAt(j + 1) == '1' )
            cnt1++;
        else
            cnt0++;
        if (mat[i + 1].charAt(j) == '1' )
            cnt1++;
        else
            cnt0++;
        if (mat[i + 1].charAt(j + 1) == '1' )
            cnt1++;
        else
            cnt0++;
        return Math.min(cnt0, cnt1);
    }
    // Function to return the minimum number
    // of slips required such that the matrix
    // contains at least a single submatrix
    // of size 2*2 with all equal elements
    function minFlips(mat , r , c)
    {
    
        // To store the result
        var res = Number.MAX_VALUE; 
        // For every submatrix of size 2*2
        for (i = 0; i < r - 1; i++)
        {
            for (j = 0; j < c - 1; j++)
            {
            
                // Update the count of flips required
                // for the current submatrix
                res = Math.min(res, minFlipsSub(mat, i, j));
            }
        }
        return res;
    }
    // Driver code
        var mat = [ "0101" , "0101" , "0101" ];
        var r = mat.length;
        var c = mat[0].length; 
        document.write(minFlips(mat, r, c));
        
// This code is contributed by Rajput-Ji
 </script>

Выход:

C++ Структуры данных

Минимум ячеек, которые нужно перевернуть, чтобы получить подматрицу 2 * 2 с равными элементами

C ++

Джава

Python 3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ