1189.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"iostream.h"
_int64 g[110],fm,fz;

int main()
{int i,j,k,n,m;char d[50][51];
cin>>n>>m;
for(i=0;i<2*n+1;i++)g[i]=0;
g[n]=1125899906842624;

for(i=0;i<n;i++)
{cin.get();
for(j=0;j<=i;j++)
{while(cin.peek()==' ')cin.get();
d[i][j]=cin.get();
}
while(cin.peek()==' ')cin.get();
d[i][j]=0;
}

for(i=0;i<n;i++)
{
for(j=n-i-1;j<=n+i+1;j+=2)
{k=j-(n-i-1);
if(k-1>0&&d[i][(k-1)/2]=='*')g[j]+=g[j-1]/2;
if(k+1<2*n&&d[i][(k+1)/2]=='*')g[j]+=g[j+1]/2;
}	

for(j=n-i;j<=n+i;j+=2)
{k=j-(n-i-1);
if(d[i][k/2]=='*')g[j]=0;
}
}
fm=1125899906842624;
fz=g[m*2];
while(fz%2==0){fz/=2;fm/=2;}
printf("%I64d/%I64d\n",fz,fm);
return 0;
}