โปรแกรมหาจำนวนเมทริกซ์ย่อยที่ไม่ใช่ศูนย์ใน C++

สมมติว่าเราได้รับเมทริกซ์ที่มีค่าเพียงสองค่า 1 วินาที และ 0 วินาที เราต้องหาจำนวนเมทริกซ์ย่อยในเมทริกซ์ที่กำหนดซึ่งมี 1s ทั้งหมด เราพิมพ์ค่าเป็นผลลัพธ์

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของเมทริกซ์
• m :=ขนาดของเมทริกซ์[0]
• กำหนดการเพิ่มขนาดอาร์เรย์:n+1 x m+1
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• สำหรับการเริ่มต้น j :=0 เมื่อ j
• บวก[i + 1, j + 1] + =เมทริกซ์[i, j]
• บวก[i + 1, j + 1] + =เพิ่ม[i, j + 1]
• บวก[i + 1, j + 1] + =เพิ่ม[i + 1, j]
• บวก[i + 1, j + 1] - =เพิ่ม[i, j]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

int solve(vector<vector<int>>& matrix) {
   int n = matrix.size();
   int m = matrix[0].size();
   int add[n + 1][m + 1];
   memset(add, 0, sizeof(add));

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         add[i + 1][j + 1] += matrix[i][j];
         add[i + 1][j + 1] += add[i][j + 1];
         add[i + 1][j + 1] += add[i + 1][j];
         add[i + 1][j + 1] -= add[i][j];
      }
   }
   int res = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         if (!matrix[i][j])
            continue;
         for (int k = 1; k <= (n - i); k++) {
            int p = 0,
               q = m - j;
            int r;
            while (p <= q) {
               int x = (p + q) / 2;
               int a = k * x;
               int cur = add[i + k][j + x] - add[i][j + x] - add[i + k][j] + add[i][j];
               if (cur == a) {
                  r = x;
                  p = x + 1;
               } else
                  q = x - 1;
            }
            if (r == 0)
               break;
            res += r;
            }
      }
   }
   return res;
}
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) <<endl;
return 0;
}

อินพุต

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

ผลลัพธ์

12