พิมพ์เซลล์ที่มีผลรวมสี่เหลี่ยมเดียวกันในเมทริกซ์ใน C++

ในปัญหานี้ เราได้รับเมทริกซ์ mat ขนาด mXn ของค่าจำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อ พิมพ์เซลล์ด้วยผลรวมสี่เหลี่ยมเดียวกันในเมทริกซ์ .

คำอธิบายปัญหา: เราจะค้นหาเซลล์ในเมทริกซ์ในลักษณะที่ ผลรวมของเมทริกซ์ย่อยที่เริ่มต้นและลงท้ายด้วยเซลล์นั้นเท่ากับผลรวมขององค์ประกอบที่เหลือทั้งหมด

สำหรับเซลล์ ผลรวมของเมทริกซ์ย่อย (a, b) เมทริกซ์ย่อย mat[0][0] ถึง mat[a][b] และ mat[a][b] ถึง mat[m][n] เท่ากับ ผลรวมขององค์ประกอบที่เหลือทั้งหมด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: เสื่อ [][] ={ {5, 0, 2, 7}
{3, 0, 1, 0}
{1, 4, 1, 3}
{10, 0, 2, 1}}

ผลลัพธ์: (2, 1)

คำอธิบาย:

สำหรับธาตุ (2,3)

เมทริกซ์ย่อย1 คือ - { {5, 0}
{3, 0}
{1, 4}}

เมทริกซ์ย่อย2 คือ - { {4, 1, 3}
{, 2, 1}}

ผลรวม =5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 =20

ผลรวมขององค์ประกอบที่เหลือ =2 + 7 + 1 + 0 + 10 =20

แนวทางการแก้ปัญหา

ในการแก้ปัญหา เราต้องสร้างเมทริกซ์ย่อยเสริม 2 ตัว aux1[m][n] และ aux2[m][n] aux1[i][j] จะเก็บผลรวมขององค์ประกอบทั้งหมดตั้งแต่ (0,0) ถึง (i, j) และ aux2[i][j] จะเก็บผลรวมขององค์ประกอบทั้งหมดจาก (i,j) ถึง ( น, ม.) จากนั้นเราจะบวกทั้งผลรวมและการลบเสื่อ (i,j) ตามที่จะเกิดขึ้นสองครั้ง

จากนั้นเราจะเปรียบเทียบผลรวมนี้กับผลรวมขององค์ประกอบทั้งหมดของเมทริกซ์ ถ้าผลรวมที่เซลล์เท่ากับครึ่งหนึ่งของผลรวมของเมทริกซ์ จากนั้นเซลล์คือผลลัพธ์ และเราจะพิมพ์ออกมา

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
#define R 4
#define C 4

void findCellWithSameRectSum(int mat[R][C]) {
   
   int m = R, n = C;
   int aux1[m][n], aux2[m][n];
   int matSum = 0;
   
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
         
         aux2[i][j] = aux1[i][j] = mat[i][j];
         matSum += mat[i][j];
         
      }
   }

   for (int i = 1; i < m; i++) {
     
      aux1[i][0] += aux1[i-1][0];
      aux2[m-i-1][n-1] += aux2[m-i][n-1];
   }

   for (int j = 1; j < n; j++) {
     
      aux1[0][j] += aux1[0][j-1];
      aux2[m-1][n-j-1] += aux2[m-1][n-j];
   }

   for (int i = 1; i < m; i++)
      for (int j = 1; j < n; j++) {
         
         aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
         aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
      }

   for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
         if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
            cout << "(" << i << ", " << j << ")\t";
}

int main() {
   int mat[R][C] = {{5, 0, 2, 7},
                {3, 0, 1, 0},
                {1, 4, 1, 3},
                {10, 0, 2, 1}};
   cout<<"The cells with same rectangular sums in a matrix is \n";
   findCellWithSameRectSum(mat);

   return 0;
}

ผลลัพธ์

The cells with same rectangular sums in a matrix is
(1, 1)           (2, 1)