Tìm số phép biến đổi để hai ma trận bằng nhau trong C ++

Trong bài toán này, chúng ta được cung cấp hai ma trận mat1 [] [] và mat2 [] [] có cùng kích thước. Nhiệm vụ của chúng ta là tìm số phép biến đổi để hai ma trận bằng nhau.

Phép biến đổi một ma trận là -

• Chọn bất kỳ ma trận nào trong hai ma trận.

• Chọn một hàng hoặc cột từ ma trận

• Thêm 1 vào tất cả các phần tử của hàng hoặc cột đã chọn.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

mat1[][] = {{1 2}
{2 1}}
mat1[][] = {{2 3}
{4 3}}

Đầu ra

3

Giải thích

1 2 => 2 2 => 2 3 => 2 3
2 1 => 3 1 => 3 2 => 4 3

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm xem liệu phép biến đổi có khả thi hay không. Đối với điều này, chúng tôi cần kiểm tra -

if( mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] != 0 )

Sau đó, không có giải pháp nào tồn tại.

Bây giờ, nếu có thể chuyển đổi, chúng tôi sẽ đếm các phép biến đổi cho các hàng và cột.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int countTransformationReq(int mat1[][MAX], int mat2[][MAX],
int m, int n) {
   for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
         mat1[i][j] -= mat2[i][j];
      for (int i = 1; i < n; i++)
         for (int j = 1; j < m; j++)
            if (mat1[i][j] - mat1[i][0] - mat1[0][j] +
               mat1[0][0] != 0)
   return -1;
   int trxCount = 0;
   for (int i = 0; i < n; i++)
      trxCount += abs(mat1[i][0]);
   for (int j = 0; j < m; j++)
      trxCount += abs(mat1[0][j] - mat1[0][0]);
   return (trxCount);
}
int main() {
   int mat1[MAX][MAX] = { {1, 2}, {2, 1}};
   int mat2[MAX][MAX] = { {2, 3}, {4, 3}};
   cout<<"The number of transformation to make the teo
   maxtrces equal are "<<countTransformationReq(mat1, mat2, 2,
   2) ;
   return 0;
}

Đầu ra

The number of transformation to make the teo maxtrces equal are 3

Cách tiếp cận hiệu quả

Một giải pháp hiệu quả hơn cho vấn đề là sử dụng công thức bắt tay.

Chúng ta sẽ tạo một mảng tạm thời [] để đếm sự xuất hiện của 0 và 1 trong mô-đun của mảng. Và sau đó trả về giá trị đếm.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include<iostream>
using namespace std;
int countEvenSumSubArray(int arr[], int n){
   int temp[2] = {1, 0};
   int count = 0, sum = 0;
   for (int i=0; i<=n-1; i++){
      sum = ( (sum + arr[i]) % 2 + 2) % 2;
      temp[sum]++;
   }
   count += (temp[0]*(temp[0]-1)/2);
   count += (temp[1]*(temp[1]-1)/2);
   return (count);
}
int main(){
   int arr[] = {2, 1, 4, 2};
   int n = sizeof (arr) / sizeof (arr[0]);
   cout<<"The count of Subarrays with even sum is "<<countEvenSumSubArray(arr, n);
   return (0);
}

Đầu ra

The count of Subarrays with even sum is 4