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

Giới thiệu

Cho hai ma trận mat1[][] và mat2[][] cùng kích thước. Mỗi phép biến đổi: chọn một ma trận, chọn một hàng hoặc cột, cộng 1 vào tất cả phần tử của hàng/cột đó. Tìm số phép biến đổi tối thiểu để hai ma trận bằng nhau.

Ví dụ minh họa

Đầu vào

mat1[][] = {{1, 2}, {2, 1}}
mat2[][] = {{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 giải

Trừ ma trận mat2 từ mat1得到 ma trận chênh lệch. Kiểm tra điều kiện khả thi:

mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] == 0

Nếu khả thi, số phép biến đổi = tổng giá trị tuyệt đối của cột đầu + tổng giá trị tuyệt đối của hàng đầu (trừ phần tử [0][0] đã tính).

Chương trình minh họa

#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 transformations to make two matrices equal are " << countTransformationReq(mat1, mat2, 2, 2);
    return 0;
}

Đầu ra

The number of transformations to make two matrices equal are 3

Lưu ý: Phần "Efficient approach" trong nội dung gốc dường như nhầm lẫn với bài toán khác (đếm mảng con tổng chẵn), không liên quan đến bài toán biến đổi ma trận.