# POJ1189总结

## 钉子和小球

### Description

，其中i为格子的编号，从左至右依次为0,1,…,n。

### Sample Input

5 2
*
* .
* * *
* . * *
* * * * *

### Sample Output

7/16

### 我的代码

dp[i][j]+=0.5*dp[i-1][j-1];
dp[i][j]+=0.5*dp[i-1][j];
dp[i][j]+=dp[i-2][j-1];

#include<stdio.h>
#include<string.h>
int n,m;
int map[51][51];
long long dp[55][55];
int check(int x,int y)
{
if (y>=1&&y<=x&&x>=1)	return 1;
else return 0;
}
long long gcd(long long x, long long y)
{
if(y==0)return x;
return gcd(y,x%y);
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int temp=0;
char c;
while(temp!=i)
{
c=getchar();
if (c=='*')	map[i][++temp]=1;
if (c=='.')	map[i][++temp]=0;
}
}
dp[1][1]=1ll<<n;
for (int i=2;i<=n+1;i++)
{
for (int j=1;j<=i;j++)
{
if (check(i-1,j-1))
{
if (map[i-1][j-1])
{
dp[i][j]+=dp[i-1][j-1]/2;
}
}
if (check(i-1,j))
{
if (map[i-1][j])
{
dp[i][j]+=dp[i-1][j]/2;
}
}
if (check(i-2,j-1))
{
if (!map[i-2][j-1])
{
dp[i][j]+=dp[i-2][j-1];
}
}
}
}
long long x=1ll<<n;
long long g=gcd(x,dp[n+1][m+1]);
printf("%lld/%lld\n",dp[n+1][m+1]/g,x/g);
return 0;
}

#include<stdio.h>
#include<string.h>
int n,m;
int map[51][51];
double dp[55][55];
int check(int x,int y)
{
if (y>=1&&y<=x&&x>=1)	return 1;
else return 0;
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int temp=0;
char c;
while(temp!=i)
{
c=getchar();
if (c=='*')	map[i][++temp]=1;
if (c=='.')	map[i][++temp]=0;
}
}
dp[1][1]=1;
for (int i=2;i<=n+1;i++)
{
for (int j=1;j<=i;j++)
{
if (check(i-1,j-1))
{
if (map[i-1][j-1])
{
dp[i][j]+=0.5*dp[i-1][j-1];
}
}
if (check(i-1,j))
{
if (map[i-1][j])
{
dp[i][j]+=0.5*dp[i-1][j];
}
}
if (check(i-2,j-1))
{
if (!map[i-2][j-1])
{
dp[i][j]+=dp[i-2][j-1];
}
}
}
}
double ans=dp[n+1][m+1];
long long int base=1LL;//!!!!!!!!!!!!!!!!!!
while((ans-(int)ans)!=0)
{
base=base*2;
ans=ans*2;
}
printf("%.0f/%lld",ans,base);
return 0;
}