Pagini recente » Cod sursa (job #373576) | Cod sursa (job #2065070) | Cod sursa (job #276400) | Cod sursa (job #1104490) | Cod sursa (job #1297882)
/*
* Code by Spiromanul
*/
#include <cstdio>
#include <cstring>
#include <fstream>
const char IN [ ] = "boundingbox.in" ;
const char OUT [ ] = "boundingbox.out" ;
const int MAX = 55 ;
using namespace std;
ofstream fout ( OUT ) ;
struct points {
int x , y ;
};
points q [ MAX ] ;
char sir [ MAX ] ;
long long dp [ MAX ] [ MAX ] [ MAX ] ;
inline int code ( int n , int x , int y )
{
return n * ( x - 1 ) + y ;
}
pair < int , int > decode ( int j , int n )
{
return make_pair ( ( j - 1 ) / n + 1 , j - ( ( j - 1 ) / n ) * n ) ;
}
int main()
{
int t ;
freopen( IN , "r" , stdin ) ;
freopen( OUT , "w" , stdout ) ;
scanf ( "%d" , &t ) ;
for ( ; t ; -- t )
{
memset( dp , 0 , sizeof ( dp ) ) ;
int n , m , nr = 0 ;
scanf ( "%d %d\n" ,&n ,&m ) ;
for ( int i = 1 ; i <= n ; ++ i )
{
gets ( sir ) ;
for ( int j = strlen ( sir ) - 1 ; j >= 0 ; -- j )
if ( sir [ j ] == '1' )
{
++ nr ;
q [ nr ].x = i ;
q [ nr ].y = j + 1 ;
}
}
int lim = n * m ;
for ( int i = 1 ; i <= nr ; ++ i )
{
if ( i != nr )
dp [ i ] [ code ( n , q [ i ].x , q [ i ].y ) ] [ code ( n , q [ i ].x , q [ i ].y ) ] = 1 ;
int punctx = q [ i ].x ;
int puncty = q [ i ].y ;
for ( int j = 1 ; j <= lim ; ++ j )
{
pair < int , int > pereche = decode ( j , n ) ;
int tempx = pereche.first ;
int tempy = pereche.second ;
int minx = min ( tempx , punctx ) ;
int miny = min ( tempy , puncty ) ;
for ( int k = 1 ; k <= lim ; ++ k )
if ( dp [ i ] [ j ] [ k ] )
{
pair < int , int > pyreche = decode ( k , n ) ;
int tempppx = pyreche.first ;
int tempppy = pyreche.second ;
int maxx = max ( tempppx , punctx ) ;
int maxy = max ( tempppy , puncty ) ;
dp [ i + 1 ] [ code ( n , minx , miny ) ] [ code ( n , maxx , maxy ) ] += dp [ i ] [ j ] [ k ] ;
dp [ i + 1 ] [ j ] [ k ] += dp [ i ] [ j ] [ k ] * 2 ;
}
}
}
long long SUM = 0 ;
for ( int j = 1 ; j <= lim ; ++ j )
for ( int k = 1 ; k <= lim ; ++ k )
if ( dp [ nr ] [ j ] [ k ] ){
pair < int , int > pereche = decode ( j , n ) ;
int tempx = pereche.first ;
int tempy = pereche.second ;
pair < int , int > pyreche = decode ( k , n ) ;
int tempppx = pyreche.first ;
int tempppy = pyreche.second ;
SUM = SUM + dp [ nr ] [ j ] [ k ] * ( tempppx - tempx + 1 ) * ( tempppy - tempy + 1 ) ;
}
/*
for ( int i = 1 ; i <= nr ; ++ i )
{
for ( int j = 0 ; j <= lim ; ++ j )
{
for ( int k = 0 ; k <= lim ; ++ k )
{
fout << dp [ i ] [ j ] [ k ] ;
}
fout << endl ;
}
fout << endl ;
}
*/
/*
for ( int i = 1 ; i <= lim ; ++ i ){
pair < int , int > pyreche = decode ( i , n ) ;
int tempppx = pyreche.first ;
int tempppy = pyreche.second ;
fout << tempppx << ' ' << tempppy << endl ;
fout << code ( n , tempppx , tempppy ) << endl ;
}
*/
while ( SUM and ! ( SUM & 1 ) )
{
SUM >>= 1 ;
-- nr ;
}
fout << SUM << '/' << ( 1LL << nr ) << '\n' ;
}
return 0;
}