ในปัญหานี้ เราได้รับเมทริกซ์ 2D ขนาด N×N และตัวแปร sum และ size งานของเราคือ การหา sub-matrix ที่มีผลรวมเท่ากับค่าที่กำหนด
เราต้องหา sub-matrix ขนาด size×size ที่ผลรวมของสมาชิกเท่ากับ sum
ตัวอย่างเพื่อความเข้าใจ
Input : mat[][] = { {1, 5, 7, 9}
{2, 4, 6, 8}
{1, 2, 5, 6}
{3, 6, 9, 3} }
sum = 22, Size = 2
Output : YES
คำอธิบาย
Submatrix ขนาด 2×2 ที่มีผลรวม 22 คือ:
{5, 7}
{4, 6}
แนวทางแก้ปัญหา
วิธีง่ายคือสร้าง submatrix ขนาด size×size ทุกตัวที่เป็นไปได้ หาผลรวมแล้วเปรียบเทียบ
วิธีที่มีประสิทธิภาพกว่า: ใช้ Dynamic Programming สร้าง DP array ที่ DP[i][j] เก็บผลรวมของสมาชิกจากแถว 0 ถึง i และคอลัมน์ 0 ถึง j จากนั้นคำนวณผลรวมของ submatrix ใดๆ ได้ใน O(1) โดยสูตร:
$$\mathrm{sum((i_s,j_s) \text{ to } (i_e,j_e)) = DP[i_e][j_e] + DP[i_s-1][j_s-1] - DP[i_s-1][j_e] - DP[i_e][j_s-1]}$$
อัลกอริทึม
- ขั้นตอนที่ 1 − สร้าง DP matrix ขนาด (n+1)×(n+1)
- ขั้นตอนที่ 2 − สำหรับแต่ละสมาชิก หาผลรวมสะสมจนถึงดัชนีนั้น
- ขั้นตอนที่ 3 − สำหรับทุกดัชนี หาผลรวม submatrix ขนาด size×size ด้วยสูตรด้านบน
- ขั้นตอนที่ 4 − หาก currSum == sum ให้คืนค่า true
- ขั้นตอนที่ 5 − คืนค่า false
ตัวอย่างโค้ด
#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 - size; i++)
for (int j = 0; j <= N - size; 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!";
return 0;
}
ผลลัพธ์
Sub-Matrix of given size having the given sum is possible!
