Pagini recente » Cod sursa (job #1275653) | Cod sursa (job #389994) | Cod sursa (job #1733412) | Cod sursa (job #31476) | Cod sursa (job #1230752)
#include <fstream>
#include <vector>
#define INF 1000
#define pii pair<int, int>
using namespace std;
int T, n, m, sum[55][55], nr1;
char mat[55][55];
long long sol, total, put[55];
vector <pii> poz;
inline long long Cmmdc(long long a, long long b)
{
long long r;
while(b)
{
r = a % b;
a = b;
b = r;
}
return a;
}
inline void Solve()
{
int i, j, nrint, xa, ya, xb, yb, arie;
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= m; ++j)
{
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i][j] - '0';
}
}
total = put[nr1];
sol = 1LL * nr1;
for(i = 0; i < nr1; ++i)
{
for(j = i + 1; j < nr1; ++j)
{
xa = min(poz[i].first, poz[j].first);
xb = max(poz[i].first, poz[j].first);
ya = min(poz[i].second, poz[j].second);
yb = max(poz[i].second, poz[j].second);
nrint = sum[xb][yb] - sum[xa - 1][yb] - sum[xb][ya - 1] + sum[xa - 1][ya - 1];
arie = (xb - xa + 1) * (yb - ya + 1);
sol += 1LL * arie * put[nrint - 2];
}
}
}
inline void Back(int pas, int xa, int ya, int xb, int yb)
{
if(pas == nr1)
{
if(xa == INF)
return;
sol += 1LL * (xb - xa + 1) * (yb - ya + 1);
return;
}
Back(pas + 1, xa, ya, xb, yb);
xa = min(xa, poz[pas].first);
ya = min(ya, poz[pas].second);
xb = max(xb, poz[pas].first);
yb = max(yb, poz[pas].second);
Back(pas + 1, xa, ya, xb, yb);
}
int main()
{
int i, j;
bool brut = true;
long long C;
put[0] = 1LL;
for(i = 1; i < 55; ++i)
put[i] = 2LL * put[i - 1];
ifstream finb("boundingbox.in");
finb >> T;
while(T--)
{
nr1 = 0;
finb >> n >> m;
for(i = 1; i <= n; ++i)
{
finb >> (mat[i] + 1);
for(j = 1; j <= m; ++j)
nr1 += mat[i][j] - '0';
}
if(nr1 > 12)
brut = false;
}
finb.close();
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
fin >> T;
while(T--)
{
nr1 = 0;
poz.clear();
fin >> n >> m;
for(i = 1; i <= n; ++i)
{
fin >> (mat[i] + 1);
for(j = 1; j <= m; ++j)
{
if(mat[i][j] == '1')
{
nr1++;
poz.push_back(make_pair(i, j));
}
}
}
sol = 0LL;
total = put[nr1];
if(brut)
Back(0, INF, INF, -INF, -INF);
else
Solve();
C = Cmmdc(sol, total);
sol /= C;
total /= C;
fout << sol << "/" << total << "\n";
}
fin.close();
fout.close();
return 0;
}