## poj1189

2019年04月18日 算法 ⁄ 共 1601字 ⁄ 字号 评论关闭

#include<iostream>
using namespace std;

__int64 Gcd(__int64 x,__int64 y)
{
if(x==y)return x;
if(x==1||y==1)return 1;

__int64 r;

if(x<y)
{
r=x;
x=y;
y=r;
}

while(y!=0)
{
r=x%y;
x=y;
y=r;
}
return x;
}

int main()
{
char mark[51][101];
__int64 sum[51][101];
__int64 finalsum;
int i,j;
int n,n1,m;
int colnum;
int spoint;
int epoint;
int count;
__int64 kinds;
__int64 maxgcd;

spoint=49;
epoint=51;
for(i=0;i<50;i++)
{
for(j=spoint;j<=epoint;j++)
{
mark[i][j]=' ';
sum[i][j]=0;
}
spoint--;
epoint++;

}
finalsum=0;

scanf("%d%d",&n,&m);

//从0行开始放钉子,放到n-1行.
//i行的钉子是从50-i开始放,比如第0行从50-0,即第50列开始方
//49行的钉子为50-49,即1列开始放

spoint=50;
for(i=0;i<n;i++)
{
colnum=i+1;//该行有多少个钉子
for(j=spoint,count=0;count<colnum;count++,j+=2)
{
scanf("%c",&mark[i][j]);
while(mark[i][j]==' '||mark[i][j]=='/n')
scanf("%c",&mark[i][j]);
}
spoint--;
}

//先初始化第0行
if(mark[0][50]=='*')
sum[0][49]=sum[0][51]=1;
else if(mark[0][50]=='.')
sum[1][50]=sum[0][50]=2;

spoint=49;
epoint=51;
//第1行的开始点
for(i=1;i<n;i++)
{
//逐步计算每行的可能性
for(j=spoint;j<=epoint;j+=2)
{
if(mark[i][j]=='*')
{
sum[i][j-1]+=sum[i-1][j];
sum[i][j+1]+=sum[i-1][j];
}

else if(mark[i][j]=='.')
{
sum[i][j]+=sum[i-1][j];
sum[i][j]+=sum[i-1][j];
sum[i+1][j]+=sum[i][j];
sum[i+1][j]+=sum[i][j];
}
}
spoint--;
epoint++;
}

n1=n-1;
spoint=50-n1-1;
epoint=50+n1+1;
for(j=spoint;j<=epoint;j+=2)
finalsum+=sum[n1][j];

kinds=sum[n1][50-n+2*m];

if(kinds==0)
{
printf("0/1/n");
return 0;
}

else
{
maxgcd=Gcd( kinds, finalsum);
kinds/=maxgcd;
finalsum/=maxgcd;
printf("%I64d",kinds);
printf("/");
printf("%I64d/n",finalsum);
return 0;
}
}