Pagini recente » Cod sursa (job #3287857) | Cod sursa (job #2535011) | Cod sursa (job #1282703) | Cod sursa (job #800248) | Cod sursa (job #1759167)
#include <fstream>
#include <vector>
#include <string>
#include <functional>
using namespace std;
int main() {
ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");
cin.tie(0);
ios_base::sync_with_stdio(false);
int num_tests; cin >> num_tests;
for (int iter = 0; iter < num_tests; iter += 1) {
int n, m; cin >> n >> m;
vector<vector<int>> partial_sum(n + 1, vector<int>(m + 1, 0));
int num_1 = 0;
for (int i = 1; i <= n; i += 1) {
string line; cin >> line;
for (int j = 1; j <= m; j += 1) {
partial_sum[i][j] = partial_sum[i - 1][j] + partial_sum[i][j - 1] - partial_sum[i - 1][j - 1] + line[j - 1] - '0';
num_1 += line[j - 1] - '0';
}
}
auto get_sum = [&](const int& x1, const int &y1, const int &x2, const int &y2) {
if (x2 < x1 || y2 < y1) {
return 0;
}
return partial_sum[x2][y2] - partial_sum[x1 - 1][y2] - partial_sum[x2][y1 - 1] + partial_sum[x1 - 1][y1 - 1];
};
long long answer = 0LL;
for (int i = 1; i <= n; i += 1) for (int j = 1; j <= m; j += 1) for (int k = i; k <= n; k += 1) for (int p = j; p <= m; p += 1) {
if (get_sum(i, j, k, j) >= 1 && get_sum(i, p, k, p) >= 1 && get_sum(k, j, k, p) >= 1 && get_sum(i, j, i, p) >= 1) {
answer = answer + (1LL << get_sum(i + 1, j + 1, k - 1, p - 1)) * (k - i + 1) * (p - j + 1);
}
}
while (num_1 > 0 && answer > 0LL && answer % 2 == 0) {
num_1 -= 1;
answer /= 2LL;
}
cout << answer << '/' << (1LL << num_1) << '\n';
}
return 0;
}