摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

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;
}