หาจำนวนการแปลงเพื่อทำให้สองเมทริกซ์เท่ากันด้วย C++

ภาพรวมปัญหา

ได้รับเมทริกซ์สองเมทริกซ์ mat1 และ mat2 ขนาดเท่ากัน การแปลง (Transformation) ที่อนุญาต:

1. เลือกเมทริกซ์ใดเมทริกซ์หนึ่ง
2. เลือกแถวหรือคอลัมน์
3. บวก 1 ให้ทุกองค์ประกอบในแถว/คอลัมน์นั้น

หาจำนวนการแปลงน้อยที่สุดเพื่อทำให้ทั้งสองเมทริกซ์เท่ากัน

ตัวอย่าง

อินพุต

mat1 = {{1, 2}, {2, 1}}
mat2 = {{2, 3}, {4, 3}}

เอาต์พุต

3

คำอธิบาย

1 2 → 2 2 → 2 3 → 2 3
2 1 → 3 1 → 3 2 → 4 3

วิธีแก้ปัญหา

เงื่อนไขที่มีคำตอบ: ต้องเป็นจริงสำหรับทุก i,j:

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

ถ้าเป็นจริง ให้คำนวณจำนวนการแปลง:

• รวม |mat[i][0]| สำหรับทุกแถว
• รวม |mat[0][j] - mat[0][0]| สำหรับทุกคอลัมน์

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100;

int countTransformationReq(int mat1[][MAX], int mat2[][MAX], int m, int n) {
    // ลบ mat2 ออกจาก mat1
    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;
}

เอาต์พุต

The number of transformation to make the two matrices equal are 3

สรุป

ปัญหานี้ลดรูปได้โดยการลบเมทริกซ์ทั้งสอง แล้วตรวจสอบความสอดคล้องของความต่างระหว่างแถวและคอลัมน์