UVA825

 1 // 题意：从左上角走到右下角，有多少条路，输入比较麻烦 = =
 2 //第一行case数，后一空行，接下来 N，M， 再N行，第一个数是行号，其后 不确定的X个数，表示此行该处不能走 
 3 //定义 f[i][j]为走到(i,j)时存在多少条路 
 4 #include<cstdio>
 5 #include<algorithm>
 6 #include<cstring>
 7 using namespace std;
 8 int g[1010][1010],f[1010][1010];
 9 void fun(int l,char str[])
10 {
11     int len=strlen(str),num=0;
12     for(int i=0;i<=len;i++) // <=len是因为如果到最后num不为零，则需要else把它存起来 
13     {
14         if(str[i]>='0' && str[i]<='9')
15             num=num*10+(str[i]-48);
16         else 
17         {
18             g[l][num]=1,num=0;
19         }
20     }
21 }
22 int main()
23 {
24     int t,n,m,line;
25     char s[1010];
26     scanf("%d",&t);
27     while(t--)
28     {        
29         scanf("%d%d",&n,&m);
30         memset(g,0,sizeof(g));
31         for(int i=0;i<n;i++)
32         {
33             scanf("%d",&line);
34             gets(s);
35             fun(line,s);
36         }        
37         memset(f,0,sizeof(f));
38         f[0][1]=1;
39         for(int i=1;i<=n;i++)
40         {
41             for(int j=1;j<=m;j++)
42             {
43                 if(g[i][j]) continue;
44                 f[i][j]=f[i-1][j] + f[i][j-1];
45             }
46         }
47         printf("%d
",f[n][m]);
48         if(t) printf("
");
49     }
50     return 0;
51 }