Cod sursa(job #1298214)

Utilizator xtreme77Patrick Sava xtreme77 Data 22 decembrie 2014 17:27:07
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.43 kb
/*
 * 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 )
        {
            int nou_x = code ( m , q [ i ].x , q [ i ].y ) ;
            int nou_y = code ( m , q [ i ].x , q [ i ].y ) ;
            dp [ i ] [ nou_x ] [ nou_y ] = 1 ;
            for ( int j = 1 ; j <= lim ; ++ j )
            {
                pair < int , int > pereche = decode ( j , m ) ;
                int tempx = pereche.first ;
                int tempy = pereche.second ;
                int minx = min ( tempx , q [ i ].x ) ;
                int miny = min ( tempy , q [ i ].y ) ;

                //fout << j << ' ' << tempx << ' ' << tempy << '\n' ;
                //fout << code ( m , tempx , tempy ) << '\n' ;

                for ( int k = 1 ; k <= lim ; ++ k )
                {
                    if ( dp [ i - 1 ] [ j ] [ k ] )
                    {
                        pair < int , int > pyreche = decode ( k , m ) ;
                        int tempppx = pyreche.first ;
                        int tempppy = pyreche.second ;
                        int maxx = max ( tempppx , q [ i ].x ) ;
                        int maxy = max ( tempppy , q [ i ].y ) ;

                        dp [ i ] [ code ( m , minx , miny ) ] [ code ( m , maxx , maxy ) ] += dp [ i - 1 ] [ j ] [ k ] ;
                        dp [ i ] [ j ] [ k ] += dp [ i - 1 ] [ j ] [ k ]  ;
                    }
                }
            }
        }
        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 , m ) ;
                    long long tempx = pereche.first ;
                    long long tempy = pereche.second ;
                    pair < int , int > pyreche = decode ( k , m  ) ;
                    long long tempppx = pyreche.first ;
                    long long tempppy = pyreche.second ;
                    SUM = SUM + dp [ nr ] [ j ] [ k ] * ( tempppx - tempx + 1 ) * ( tempppy - tempy + 1 ) ;
                    //fout << "adun de " << dp [ nr ] [ j ] [ k ] << " ori " << " ( aria este : " << ( tempppx - tempx + 1 ) * ( tempppy - tempy + 1 ) << ")" ;
                    //fout << "submatricea " << tempx << ',' << tempy << ' ' << tempppx << ',' << tempppy << '\n' ;
                }
        /*
        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 ;
        }
        */
        assert ( SUM >= 0 ) ;
        while ( SUM and ! ( SUM & 1 ) )
        {
            SUM >>= 1 ;
            -- nr ;
        }
        fout << SUM << '/' << ( 1LL << nr ) << '\n' ;
    }

    return 0;
}