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
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 int mod = 1e9+
7;
6 int dp[
33][
33];
7 using namespace std;
8 int main()
9 {
10 int t;
11 scanf(
"%d",&
t);
12 while(t--
)
13 {
14 int n,x,y;
15 scanf(
"%d %d %d",&n,&x,&
y);
16 memset(dp,
0,
sizeof(dp));
17 dp[
1][
0]=
1;
18 for(
int i =
1;i <= n;i++
)
19 {
20 for(
int j =
1;j <= n;j++
)
21 {
22 if(i == x&&j ==
y)
23 continue;
24 dp[i][j]=(dp[i-
1][j]+dp[i][j-
1])%
mod;
25 }
26 }
27 if(dp[n][n]==
0)
28 printf(
"-1\n");
29 else
30 printf(
"%d\n",dp[n][n]);
31 }
32 return 0;
33 }
View Code
转载于:https://www.cnblogs.com/llal/p/5753639.html
相关资源:JAVA上百实例源码以及开源项目