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