Cod sursa(job #1463050)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 19 iulie 2015 21:26:38
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int nmax = 55;

char a[nmax][nmax];
int s[nmax][nmax];
ll two[nmax];

int sum(int i, int j, int k, int l) {
	return s[k][l] - s[k][j - 1] - s[i - 1][l] + s[i - 1][j - 1];
}

int main() {

	two[0] = 1;
	for (int i = 1; i < nmax; i++)
		two[i] = 2LL * two[i - 1];

	int t;
	fin >> t;

	for (; t; t--) {
		int n, m;
		fin >> n >> m;

		for (int i = 1; i <= n; i++)
			fin >> (a[i] + 1);

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] - '0';

		int cnt = 0;
		ll total = 0;

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				for (int k = i; k <= n; k++)
					for (int l = j; l <= m; l++) {
						if (i == k && j == l && a[i][j] == '1') {
							cnt++;
							total++;
						} else if (i == k && a[i][j] == '1' && a[i][l] == '1') {
							total += two[sum(i, j + 1, i, l - 1)] * (l - j + 1);
						} else if (j == l && a[i][j] == '1' && a[k][j] == '1') {
							total += two[sum(i + 1, j, k - 1, j)] * (k - i + 1);
						} else {
							for (int mask = 0; mask < 16; mask++) {
								if ((mask & 1) && a[i][j] == '0')
									continue;
								if ((mask & 2) && a[i][l] == '0')
									continue;
								if ((mask & 4) && a[k][j] == '0')
									continue;
								if ((mask & 8) && a[k][l] == '0')
									continue;

								ll curr = two[(sum(i + 1, j + 1, k - 1, l - 1))];

								if ((mask & 1) || (mask & 2))
									curr *= 1LL * two[sum(i, j + 1, i, l - 1)];
								else
									curr *= 1LL * (two[sum(i, j + 1, i, l - 1)] - 1);

								if ((mask & 1) || (mask & 4))
									curr *= 1LL * two[sum(i + 1, j, k - 1, j)];
								else
									curr *= 1LL * (two[sum(i + 1, j, k - 1, j)] - 1);

								if ((mask & 2) || (mask & 8))
									curr *= 1LL * two[sum(i + 1, l, k - 1, l)];
								else
									curr *= 1LL * (two[sum(i + 1, l, k - 1, l)] - 1);

								if ((mask & 4) || (mask & 8))
									curr *= 1LL * two[sum(k, j + 1, k, l - 1)];
								else
									curr *= 1LL * (two[sum(k, j + 1, k, l - 1)] - 1);

								total += curr * (k - i + 1) * (l - j + 1);
							}
						}
					}

		ll g = __gcd(total, two[cnt]);
		fout << total / g << "/" << two[cnt] / g << '\n';
	}

	return 0;
}