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

Код:
#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 ;
}