Cod sursa(job #1230928)

Utilizator darrenRares Buhai darren Data 19 septembrie 2014 13:08:38
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 2.53 kb
#include <fstream>
#include <algorithm>

using namespace std;

int T, N, M;
char A[52][52];
int S[52][52];
long long result;

int getsum(int i1, int j1, int i2, int j2)
{
	return S[i2][j2] - S[i2][j1 - 1] - S[i1 - 1][j2] + S[i1 - 1][j1 - 1];
}

int main()
{
	ifstream fin("boundingbox.in");
	ofstream fout("boundingbox.out");
	
	fin >> T;
	while (T--)
	{
		fin >> N >> M;
		for (int i = 1; i <= N; ++i)
			fin >> (A[i] + 1);
		
		int ones = 0;
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j)
			{
				ones += (A[i][j] == '1');
				S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (A[i][j] == '1');
			}
		
		result = 0;
		for (int i1 = 1; i1 <= N; ++i1)
			for (int j1 = 1; j1 <= M; ++j1)
				for (int i2 = i1; i2 <= N; ++i2)
					for (int j2 = j1; j2 <= M; ++j2)
					{
						int area = (i2 - i1 + 1) * (j2 - j1 + 1);
						
						int up = getsum(i1, j1, i1, j2);
						int rg = getsum(i1, j2, i2, j2);
						int dw = getsum(i2, j1, i2, j2);
						int lf = getsum(i1, j1, i2, j1);
						
						if (i1 == i2 && j1 == j2)
						{
							if (A[i1][j1] == '1') result += area;
							continue;
						}
						if (i1 == i2)
						{
							if (A[i1][j1] == '1' && A[i1][j2] == '1') result += area * (1LL << (up - 2));
							continue;
						}
						if (j1 == j2)
						{
							if (A[i1][j1] == '1' && A[i2][j1] == '1') result += area * (1LL << (rg - 2));
							continue;
						}
						
						int mask = 0;
						if (A[i1][j1] == '1') mask |= (1 << 0), --lf, --up;
						if (A[i1][j2] == '1') mask |= (1 << 1), --up, --rg;
						if (A[i2][j2] == '1') mask |= (1 << 2), --rg, --dw;
						if (A[i2][j1] == '1') mask |= (1 << 3), --dw, --lf;
						
						for (int k = 0; k < (1 << 4); ++k)
							if ((mask | k) == mask)
							{
								long long pnow = 1;
								if ((k & (1 << 0)) || (k & (1 << 1))) pnow *= (1LL << up);
								else                                  pnow *= (1LL << up) - 1;
								if ((k & (1 << 1)) || (k & (1 << 2))) pnow *= (1LL << rg);
								else                                  pnow *= (1LL << rg) - 1;
								if ((k & (1 << 2)) || (k & (1 << 3))) pnow *= (1LL << dw);
								else                                  pnow *= (1LL << dw) - 1;
								if ((k & (1 << 3)) || (k & (1 << 0))) pnow *= (1LL << lf);
								else                                  pnow *= (1LL << lf) - 1;
								
								result += area * pnow;
							}
					}
		
		while (ones && result % 2 == 0)
		{
			result /= 2;
			--ones;
		}
		
		if (result == 0) fout << "0/1\n";
		else             fout << result << '/' << (1LL << ones) << '\n';
	}
	
	fin.close();
	fout.close();
}