Cod sursa(job #1298041)

Utilizator xtreme77Patrick Sava xtreme77 Data 22 decembrie 2014 15:13:32
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.07 kb
/*
 * Code by Spiromanul
 */


#include <cstdio>
#include <cstring>
#include <fstream>
#include <assert.h>

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 ] ;

struct Huge_number
{
    public: int v[20],BASE=1000000000;
    public:
        Huge_number() {v[0]=1;}
        void set(int x)
        {
            memset(v,0,sizeof(v));
            do
            {
                v[++v[0]]=x%BASE;
                x/=BASE;
            }while(x);
        }
        void mul( int B )
        {
            int i ;
            long long t = 0;
            for (i = 1; i <= v[0] || t; i++, t /= BASE)
                    v[i] = (t += v[i] * B) % BASE;
            v[0] = i - 1;
        }
        void div( )
        {
            int i ;
            long long t = 0;
            for (i = v[0]; i > 0; i--, t &= 1 )
                    v[i] = (t = t * BASE + v[i]) >> 1 ;
            for (; v[0] > 1 && !v[v[0]]; v[0]--);
        }
        void print()
        {
            printf("%d",v[v[0]]);
            for(int i=v[0]-1;i;i--)
                printf("%09d",v[i]);
            //printf("\n");
        }
        void operator+=(const Huge_number&other)
        {
            v[0]=max(v[0],other.v[0]);
            int t=0;
            for(int i=1;i<=v[0];i++)
            {
                v[i]=v[i]+other.v[i]+t;
                t=v[i]/BASE;
                v[i]%=BASE;
            }
            if(t)
                v[++v[0]]=t;
        }
} dp [ MAX ] [ MAX ] [ MAX ] , SUM ;

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 )
    {
        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 )
            for ( int j = 1 ; j <= lim ; ++ j )
                for ( int k = 1 ; k <= lim ; ++ k )
                    dp [ i ] [ j ] [ k ].set ( 0 ) ;
        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 ) ].set ( 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 [ nr ] [ j ] [ k ].v [ 0 ] )
                    {
                        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 ] ;
                        dp [ i + 1 ] [ j ] [ k ] += dp [ i ] [ j ] [ k ] ;
                    }
            }
        }

        SUM.set ( 0 ) ;
        for ( int j = 1 ; j <= lim ; ++ j )
            for ( int k = 1 ; k <= lim ; ++ k )
                if ( dp [ nr ] [ j ] [ k ].v [ 0 ] )
                {
                    pair < int , int > pereche = decode ( j , n ) ;
                    long long tempx = pereche.first ;
                    long long tempy = pereche.second ;
                    pair < int , int > pyreche = decode ( k , n ) ;
                    long long tempppx = pyreche.first ;
                    long long tempppy = pyreche.second ;
                    dp [ nr ] [ j ] [ k ].mul ( ( tempppx - tempx + 1 ) ) ;
                    dp [ nr ] [ j ] [ k ].mul ( ( tempppy - tempy + 1 ) ) ;
                    SUM += dp [ nr ] [ j ] [ k ] ;
                }
        /*
        int op = 0 ;
        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 ] << ' ' ;
                    if ( dp [ i ] [ j ] [ k ] < 0 ){
                        op ++ ;
                        fout << i << ' ' << j << ' ' << k ;
                        return 0 ;
                    }
                }
                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 ;
        }
        */
        /*
        if ( SUM < 0 )
        {
            fout << op << endl ;
            fout << "STOP" ;
            return 0 ;
        }
        */
        while ( SUM.v[ 0 ] and !( SUM.v[ 1 ] & 1 )  )
        {
            SUM.div ( ) ;
            -- nr ;
        }
        SUM.print() ;
        printf ( "/%lld\n" , 1LL << nr ) ;
    }

    return 0;
}