Cod sursa(job #1297882)

Utilizator xtreme77Patrick Sava xtreme77 Data 22 decembrie 2014 13:36:26
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.97 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 )
        {
            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;
}