DP计数（UVA 885&&POJ 2704)(二)

The number of different minimal paths from the park to the station avoiding underground passages.

Sample Input

1

4 5
1
2 2
3 3 5
4

Sample Output

4

#include
         
          
#include
          
            #include
           
             #include
            
              #include
             
               typedef long long LL; using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) int t,w,n; char str[1100]; int mp[1100][1100]; int dp[1100][1100]; int main() { std::ios::sync_with_stdio(false); scanf("%d",&t);int x; while(t--) { scanf("%d%d",&w,&n); getchar(); CLEAR(mp,0); CLEAR(dp,0); REPF(i,1,w) { scanf("%d",&x); gets(str); int len=strlen(str); int cnt=0; REPF(j,0,len) { if(str[j]-'0'>=0&&str[j]-'0'<=9) cnt=cnt*10+str[j]-'0'; else { mp[x][cnt]=1; cnt=0; } } } dp[0][1]=1; REPF(i,1,w) { REPF(j,1,n) { if(mp[i][j]==1) dp[i][j]=0; else dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } printf("%d\n",dp[w][n]); if(t) puts(""); } return 0; }