Cod sursa(job #1238483)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 7 octombrie 2014 00:24:39
Problema Boundingbox Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#include <cstring>
#include <algorithm>

#define maxdim 105

using namespace std;

int n, m;
int x[maxdim], y[maxdim];
long long D[maxdim][maxdim][maxdim];

int main() {
	
	freopen("boundingbox.in", "r", stdin);
	freopen("boundingbox.out", "w", stdout);
	
	int tests;
	scanf("%d", &tests);
	while (tests--) {
		
		scanf("%d %d\n", &n, &m);
		int ones = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				char ch;
				scanf("%c", &ch);
				if (ch == '1') {
					++ones;
					x[ones] = i, y[ones] = j;
				}
			}
			scanf("\n");
		}
		
		for (int i = 0; i <= ones; ++i) {
			for (int x1 = 0; x1 <= n; ++x1) {
				for (int x2 = 0; x2 <= n; ++x2) {
					for (int y1 = 0; y1 <= m; ++y1) {
						for (int y2 = 0; y2 <= m; ++y2) {
							D[i][x1 * (m+1) + y1][x2 * (m+1) + y2] = 0;
						}
					}
				}
			}
		}
		
		D[0][n * (m+1) + m][0] = 1;
		for (int i = 0; i < ones; ++i) {
			
			for (int x1 = 0; x1 <= n; ++x1) {
				for (int x2 = 0; x2 <= n; x2 = (x2 == 0 ? max(x1, 1) : x2 + 1)) {
					for (int y1 = 0; y1 <= m; ++y1) {
						for (int y2 = 0; y2 <= m; y2 = (y2 == 0 ? max(y1, 1) : y2+1)) {
							if (D[i][x1 * (m+1) + y1][x2 * (m+1) + y2] == 0) {
								continue;
							}
							
							D[i+1][x1 * (m+1) + y1][x2 * (m+1) + y2] += D[i][x1 * (m+1) + y1][x2 * (m+1) + y2]; //nu intra in solutie
							D[i+1][min(x1, x[i+1]) * (m+1) + min(y1, y[i+1])][max(x2, x[i+1]) * (m+1) + max(y2, y[i+1])] += D[i][x1 * (m+1) + y1][x2 * (m+1) + y2];
						}
					}
				}
			}
		}
		
		long long total_sum = 0;
		for (int x1 = 1; x1 <= n; ++x1) {
			for (int x2 = x1; x2 <= n; ++x2) {
				for (int y1 = 1; y1 <= m; ++y1) {
					for (int y2 = y1; y2 <= m; ++y2) {
						
						total_sum += (x2 - x1 + 1) * (y2 - y1 + 1) * D[ones][x1 * (m+1) + y1][x2 * (m+1) + y2];
					}
				}
			}
		}
		
		long long numitor = 1LL << ones;
		for (int i = 1; numitor != 1 && !(total_sum & 1); ++i) {
			total_sum >>= 1;
			numitor >>= 1;
		}
		
		printf("%lld/%lld\n", total_sum, numitor);
	}
	
	return 0;
}