ধরা যাক একটি ম্যাট্রিক্স দেওয়া আছে যাতে শুধু ০ এবং ১ রয়েছে। আমাদের সেই সাবম্যাট্রিক্সগুলো বের করতে হবে যাতে সব উপাদান ১। এমন সাবম্যাট্রিক্সের সংখ্যা প্রিন্ট করতে হবে।
উদাহরণস্বরূপ, ম্যাট্রিক্স = {{0,0,1,0},{0,1,0,0},{0,1,0,1},{1,1,0,1}} হলে আউটপুট হবে ১২।
সমাধানের ধাপসমূহ
- n := ম্যাট্রিক্সের রো সংখ্যা, m := কলাম সংখ্যা
- আকার (n+1) x (m+1) এর একটি ২D প্রিফিক্স সম অ্যারে add তৈরি করুন
- প্রতিটি সেল (i, j) এর জন্য ২D প্রিফিক্স সম হিসাব করুন: add[i+1][j+1] = matrix[i][j] + add[i][j+1] + add[i+1][j] - add[i][j]
- res := ০
- প্রতিটি সেল (i, j) যেটি ১ হয়, তার জন্য:
- উচ্চতা k = 1 থেকে n-i পর্যন্ত লুপ চালান
- বাইনারি সার্চ দিয়ে চওড়া x বের করুন যাতে সাবম্যাট্রিক্সের সকল উপাদান ১ হয়
- প্রিফিক্স সম ব্যবহার করে সাবম্যাট্রিক্সের যোগফল যাচাই করুন
- সর্বোচ্চ বৈধ চওড়া r যোগ করুন res-এ
- res রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
#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, 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
