Contest

题目链接：http://acm.zzuli.edu.cn/zzuliacm/problem.php?cid=1157&pid=2

Description

985走入了一个n * n的方格地图，他已经知道其中有一个格子是坏的。现在他要从(1, 1)走到(n, n)，每次只可以向下或者向右走一步，问他能否到达（n，n）。若不能到达输出-1，反之输出到达（n，n）的方案数。

Input

第一行输入一个整数t，代表有t组测试数据。

每组数据第一行输入三个整数n，x，y，分别代表方格地图的大小以及坏掉格子的位置。

注：1 <= t <= 20，1 <= n <= 30，1 <= x，y <= n。

Output

若可以到达（n，n）则输出方案数对1e9 + 7取余的结果，反之输出-1。

Sample Input

2
2 1 2
2 2 2 
Sample Output

1
-1

分析:组合数/dp

dp:

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<ctype.h>
 5 #include<stdlib.h>
 6 #include <iostream>
 7 #include<algorithm>
 8 #include<queue>
 9 #define N 100
10 using namespace std;
11 
12 int main()
13 {
14     int T,i,n,j,dp[N][N],x,y;
15 
16     scanf("%d", &T);
17 
18     while(T--)
19     {
20         scanf("%d %d %d", &n,&x,&y);
21         memset(dp,0,sizeof(dp));
22 
23         for(i=1; i<=n; i++)
24             for(j=1; j<=n; j++)
25             {
26                 if(i==x&&j==y)///1
27                     dp[i][j]=0;
28                 else  if(i==1&&j==1)///2
29                     dp[i][j]=1;///1和2顺序反了，wa~wa~wa~
30                 else
31                     dp[i][j]=dp[i-1][j]+dp[i][j-1];
32 
33                 dp[i][j]%=1000000007;
34             }
35 
36         if(dp[n][n]==0)
37             printf("-1
");
38         else
39             printf("%d
", dp[n][n]);
40     }
41     return 0;
42 }

组合数：

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<ctype.h>
 5 #include<stdlib.h>
 6 #include <iostream>
 7 #include<algorithm>
 8 #include<queue>
 9 #define N 10005
10 using namespace std;
11  
12 long long c(long long n,long long m)
13 {
14     if(m > n/2)
15     m = n-m;
16     long long a =1, b =1;
17     for(int i =1; i <= m; i++)
18     {
19         a *= n-i+1;
20         b *= i;
21         if(a % b ==0)
22         {
23             a /= b;
24             b =1;
25         }
26     }
27     return a/b;
28 }
29 int main()
30 {
31     int t, n, x, y;
32     scanf("%d", &t);
33     while(t--)
34     {
35         scanf("%d%d%d", &n, &x, &y);
36         if((x == 1 && y == 1)||(x == n && y == n))
37         {
38             printf("-1
");
39             continue;
40         }
41         else
42         {
43             long long a = c(n*2-2, n-1);
44             long long b = c(n*2-x-y, n-x) * c( x+y-1-1, x-1);
45             int ans = (a-b)%1000000007;
46             printf("%d
", ans);
47         }
48     }
49     return 0;
50 }
51