• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Contest-多校训练(985专场)ProblemC:985的方格难题

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目链接: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\n");
38         else
39             printf("%d\n", 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\n");
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\n", ans);
47         }
48     }
49     return 0;
50 }
51  

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
招聘C#.net程序员[温州医学院]发布时间:2022-07-14
下一篇:
C#实现office文档转换为PDF或xps的一些方法--zt发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap