http://acm.pku.edu.cn/JudgeOnline/problem?id=1189

http://acm.pku.edu.cn/JudgeOnline/images/1189_2.jpg

Код:
#include <iostream>
#include <string>
using namespace std;

struct  FMDATA
{
    __int64 a, b;
} ;

__int64 gcd(__int64 a, __int64 b)
{
     if  (b  ==   0 )
         return  a;
     else
         return  gcd(b, a % b);
}

__int64 lcm(__int64 a, __int64 b)
{
     if  (a  ==   0   ||  b  ==   0 )
         return   0 ;
     else
     if  (a  >  b)
         return  a / gcd(a,b) * b;
     else
         return  b / gcd(a,b) * a;
}

__int64 add(FMDATA t1, FMDATA t2, FMDATA  & result)
{
    __int64 t;
    result.b  =  lcm(t1.b, t2.b);
    result.a  =  result.b / t1.b * t1.a  +  result.b / t2.b * t2.a;
    t  =  gcd(result.a, result.b);
    result.b  /=  t;
    result.a  /=  t;
     return   0 ;
}

int  main()
{
     char  c[100][100];
     char  enter[10001];
    FMDATA dp[100][100];
    FMDATA tmp1, tmp2, tmp3;
    __int64 i, j, k, t, p, q;
    __int64 n, m;
     while  (scanf( "%I64d%I64d" ,  &n,  &m)  !=  EOF)
     {
        gets(enter);
         for  (i = 1 ; i <= n; i ++ )
         {
            gets(enter);
            k  =   1 ;
             for  (j = 0 ; j < strlen(enter); j ++ )
             {
                 if  (enter[j]  ==   '*'   ||  enter[j]  ==   '.' )
                    c[i][k ++ ]  =  enter[j];
            }
        }
         for  (i = 1 ; i <= n + 1 ; i ++ )
            c[n + 1 ][i]  =   '*' ;
         for  (i = 1 ; i <= n + 1 ; i ++ )
         {
             for  (j = 1 ; j <= i; j ++ )
             {
                dp[i][j].a  =   0 ;
                dp[i][j].b  =   1 ;
            }
        }
         for  (i = 1 ; i <= n; i += 2 )
         {
            t  =  (i + 1 ) / 2 ;
             if  (c[i][t]  ==   '*' )
             {
                dp[i][t].a  =   1 ;
                 break ;
            }
        }
        k  =  i;
         if  (i > n)
         {
             if  ((n + 2 ) / 2   ==  m + 1 )
                printf( "1/1\n" );
             else
                printf( "0/1\n" );
             continue ;
        }
         for  (i = k + 1 ; i <= n + 1 ; i ++ )
         {
             for  (j = 1 ; j <= i; j ++ )
             {
                tmp1.a  =   0 ;
                tmp1.b  =   1 ;
                 if  (i - 1   >=   1   &&  j  <=  i - 1   &&  j  >=   1   &&  c[i - 1 ][j]  ==   '*' )
                 {
                    tmp1.a  =  dp[i - 1 ][j].a;
                    tmp1.b  =  dp[i - 1 ][j].b  *   2 ;
                }
                tmp2.a  =   0 ;
                tmp2.b  =   1 ;
                 if  (i - 1   >=   1   &&  j - 1   <=  i - 1   &&  j - 1   >=   1   &&  c[i - 1 ][j - 1 ]  ==   '*' )
                 {
                    tmp2.a  =  dp[i - 1 ][j - 1 ].a;
                    tmp2.b  =  dp[i - 1 ][j - 1 ].b  *   2 ;
                }
                add(tmp1, tmp2, dp[i][j]);
                tmp3.a  =   0 ;
                tmp3.b  =   1 ;
                 if  (i - 2   >=   1   &&  j - 1   <=  i - 2   &&  j - 1   >=   1   &&  c[i - 2 ][j - 1 ]  ==   '.' )
                 {
                    tmp3.a  =  dp[i - 2 ][j - 1 ].a;
                    tmp3.b  =  dp[i - 2 ][j - 1 ].b;
                }
                add(tmp3, dp[i][j], dp[i][j]);
            }
        }
        printf( "%I64d/%I64d\n" , dp[n + 1 ][m + 1 ].a, dp[n + 1 ][m + 1 ].b);
    }
  system("pause");
  return   0 ;
}