Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình đếm số lượng mẫu vuông con của 1s trong ma trận đã cho trong C ++

Giả sử chúng ta có một ma trận nhị phân 2d, chúng ta phải tìm tổng số ma trận con có tất cả 1 s.

Vì vậy, nếu đầu vào giống như

1 1 0
1 1 0
0 0 1

thì đầu ra sẽ là 10, vì có năm ma trận 1 x 1, hai ma trận 2 x 1. hai ma trận 1 x 2. Và một ma trận 2 x 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm getAns (), điều này sẽ nhận một mảng a,

  • ret:=0

  • n:=kích thước của một

  • Xác định một mảng v có kích thước n

  • Xác định một ngăn xếp

  • để khởi tạo i:=0, khi i

    • while (st không trống và là [phần tử trên cùng của st]> =a [i]), do -

      • bật từ st

    • nếu st không trống, thì -

      • trước:=phần tử hàng đầu của st

      • v [i]:=v [i] + v [trước]

      • v [i]:=v [i] + a [i] * (i - trước)

    • Nếu không

      • v [i]:=v [i] + a [i] * (i + 1)

    • chèn tôi vào st

  • cho mỗi tôi trong v -

    • ret:=ret + i

  • trả lại ret

  • Từ phương thức chính, thực hiện như sau -

  • ret:=0

  • n:=kích thước của v

  • m:=(nếu n khác 0 thì kích thước của v [0], ngược lại là 0)

  • Xác định nhiệt độ mảng có kích thước m

  • để khởi tạo i:=0, khi i

    • để khởi tạo j:=0, khi j

      • temp [j]:=(nếu v [i, j] khác 0 thì temp [j] + 1, nếu không thì 0)

    • ret:=ret + getAns (tạm thời)

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int getAns(vector& a) {
      int ret = 0;
      int n = a.size();
      vector<int> v(n);
      stack<int> st;
      for (int i = 0; i < a.size(); i++) {
         while (!st.empty() && a[st.top()] >= a[i])
            st.pop();
         if(!st.empty()) {
            int prev = st.top();
            v[i] += v[prev];
            v[i] += a[i] * (i - prev);
         }
         else{
            v[i] += a[i] * (i + 1);
         }
         st.push(i);
      }
      for (int i : v) {
         ret += i;
      }
      return ret;
   }
   int solve(vector<vector<int>>& v) {
      int ret = 0;
      int n = v.size();
      int m = n ? v[0].size() : 0;
      vector<int> temp(m);
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            temp[j] = v[i][j] ? temp[j] + 1 : 0;
         }
         ret += getAns(temp);
      }
      return ret;
   }
};
int solve(vector<vector<int>>& matrix) {
   return (new Solution())->solve(matrix);
}
main(){
   vector<vector> matrix = {
      {1, 1, 0},
      {1, 1, 0},
      {0, 0, 1}
   };
   cout << solve(matrix);
}

Đầu vào 

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

Đầu ra 

10