โปรแกรมหาจำนวนซับแมทริกซ์ที่ผลรวมเท่าค่าเป้าหมายใน C++

สมมติว่าเราได้รับแมทริกซ์ที่มีค่าจำนวนเต็ม เราต้องหาจำนวนซับแมทริกซ์ที่ผลรวมของสมาชิกเท่ากับค่าเป้าหมาย (target sum) ที่กำหนด

เช่น หากอินพุตเป็นแมทริกซ์ 4x4 ดังนี้:

และ target = 5 ผลลัพธ์จะเป็น 3

ขั้นตอนการแก้ปัญหา

• n := จำนวนแถวของ mat, m := จำนวนคอลัมน์
• ถ้า m > n ให้ทรานสโพสแมทริกซ์แล้วเรียกฟังก์ชันซ้ำ
• ans := 0
• วนลูปคอลัมน์เริ่มต้น p จาก 0 ถึง m-1:
  • สร้างอาเรย์ arr ขนาด n
  • วนลูปคอลัมน์สิ้นสุด q จาก p ถึง m-1:
    • อัปเดต arr[i] += mat[i][q] สำหรับทุกแถว i
    • ใช้ Hash Map (pcnt) เก็บความถี่ของผลรวมคำนำหน้า เริ่มต้น {0: 1}
    • pref := 0
    • วนลูป i จาก 0 ถึง n-1:
      • pref += arr[i]
      • ถ้ามี (pref - sumTarget) ใน pcnt: ans += pcnt[pref - sumTarget]
      • pcnt[pref]++
• คืนค่า ans

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

#include <bits/stdc++.h> using namespace std; int solve(vector<vector<int>>& mat, int sumTarget) {    int n = mat.size();    int m = n == 0 ? 0 : mat[0].size();    if (m > n) {       vector<vector<int>> transpose(m, vector<int>(n));       for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) transpose[j][i] = mat[i][j];       return solve(transpose, sumTarget);    }    int ans = 0;    for (int p = 0; p < m; p++) {       vector<int> arr(n);       for (int q = p; q < m; q++) {          for (int i = 0; i < n; i++) arr[i] += mat[i][q];          unordered_map<int, int> pcnt = {{0, 1}};          int pref = 0;          for (int i = 0; i < n; i++) {             pref += arr[i];             auto tmp = pcnt.find(pref - sumTarget);             if (tmp != end(pcnt)) ans += tmp->second;             pcnt[pref]++;          }       }    }    return ans; } int main() {    vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}; cout << solve(mat, 5) << endl; return 0; }

อินพุต

{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}, 5

เอาต์พุต

3