Pagini recente » Cod sursa (job #446588) | Cod sursa (job #2951745) | Cod sursa (job #1435262) | Cod sursa (job #113906) | Cod sursa (job #1230928)
#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();
}