ค้นหาเมทริกซ์ย่อยด้วยผลรวมที่กำหนดใน C++

ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติที่มีขนาด N*N และผลรวมและขนาดตัวแปรสองตัว งานของเราคือ ค้นหาเมทริกซ์ย่อยด้วยผลรวมที่กำหนด .

เราต้องหาเมทริกซ์ย่อยของ size*size โดยมีผลรวมขององค์ประกอบเท่ากับผลรวม

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

Input : mat[][] = {
   {1, 5, 7, 9}
   {2, 4, 6, 8}
   {1, 2, 5, 6}
   {3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES

คำอธิบาย −

The submatrix of size k with sum 22 is
{5, 7}
{4, 6}

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

วิธีแก้ปัญหาอย่างง่ายคือการสร้างอาร์เรย์ย่อยที่มีขนาด*ขนาดที่เป็นไปได้ทั้งหมด ค้นหาผลรวมแล้วนำมาเท่ากันกับค่าผลรวมที่กำหนด ส่งคืนหากทั้งคู่เท่ากัน

อีกวิธีหนึ่งคือการใช้แนวคิดของ ไดนามิกอัลกอริธึมการเขียนโปรแกรม . ในวิธีนี้ เราจะสร้างอาร์เรย์ DP ซึ่งจะเก็บผลรวมจนถึงค่าดัชนีปัจจุบัน เช่น DP[i][j] จะเก็บผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์จากดัชนีแถว 0 ถึง i และดัชนีคอลัมน์ 0 ถึง j .

การใช้อาร์เรย์ DP นี้ เราจะคำนวณผลรวมระหว่างดัชนีเริ่มต้นและดัชนีสิ้นสุดโดยใช้สูตร

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[ i_s][i_e]\:-\:DP[i_e][i_s]}$$

อัลกอริทึม

ขั้นตอนที่ 1 − สร้างเมทริกซ์ขนาด DP (n+1)*(n+1)

ขั้นตอนที่ 2 − สำหรับแต่ละองค์ประกอบของเมทริกซ์ ให้หาผลรวมจนถึงดัชนีปัจจุบัน

ขั้นตอนที่ 3 − สำหรับดัชนีทั้งหมดตั้งแต่ 0 ถึง n ให้หาผลรวมของเมทริกซ์ย่อยของขนาด ขนาด*ขนาด โดยใช้สูตรและเก็บเป็น currSum

ขั้นตอนที่ 4 − ถ้า currSum ==sum คืนค่าเป็น true

ขั้นตอนที่ 5 − คืนค่าเท็จ

ตัวอย่าง

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

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

ผลลัพธ์

Sub-Matrix of given size having the given sum is possible!