ACM 825 Q825: Walking on the Safe Side
DP
當你學到排列組合之時 就會知道該怎麼填了
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
int n;
char x[500];
scanf("%d",&n);
{
int a,b,c,d,n1,m1;
for(a=0;a<n;a++)
{
unsigned long long int ans[101][101]={0};
int map[101][101]={0};
scanf("%d %d ",&n1,&m1);/*神奇的空格不可忽略*/
for(b=1;b<=n1;b++)
{
gets(x);
int m=strlen(x),temp=0,temp2=0;
for(c=0;c<m;c++)
{
if(x[c]==' ') break;
temp2=temp2*10+x[c]-48;
}
if(c==m) continue;
for(c=c+1;c<m;c++)
{
if(x[c]<=57&&x[c]>=48) temp=temp*10+x[c]-48;
else
{
map[temp2][temp]=-1;
temp=0;
}
}
map[temp2][temp]=-1;
}
/*以上為輸入的處理 以-1代表不能走*/
if(map[1][1]!=-1) ans[1][1]=1;
for(c=1;c<=n1;c++)
for(d=1;d<=m1;d++)
{
if(map[c][d]!=-1)
{
ans[c][d]+=ans[c-1][d];
ans[c][d]+=ans[c][d-1];
}
}
printf("%llu\n",ans[n1][m1]);
if(a!=n-1) printf("\n");
}
}
return 0;
}
上一篇:ACM 514 Rails