【985系列】985的方格难题

谁践踏了优雅 2022-09-25 06:20 87阅读 0赞

## 1894: 985的方格难题 ##

Time Limit: 1 Sec Memory Limit:  128 MB  
Submit: 450 Solved: 99  
  
[Submit][] [Status][] [Web Board][]

## 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

## HINT ##

## Source ##

[hpu][]

递推吧，勉强算是动态规划，搜索的话会超时。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #define LL long long
    using namespace std;
    const int N = 33;
    LL map[N][N];
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		int n,x,y;
    		scanf("%d%d%d",&n,&x,&y);
    		memset(map,0,sizeof(map));
    		for(int i=1; i<=n; i++) {
    			for(int j=1; j<=n; j++) {
    				if(i==x&&j==y)
    					map[i][j]=0;
    				else if(i==1&&j==1)
    					map[i][j]=1;
    				else
    					map[i][j]=map[i][j-1]+map[i-1][j];
    			}
    		}
    		if(!map[n][n])    //此处不能用if(x==n&&y==n)
    			printf("-1\n");
    		else
    			printf("%d\n",map[n][n]%1000000007);
    	}
    	return 0;
    }

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1894
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1894
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1894
[hpu]: http://acm.zzuli.edu.cn/zzuliacm/problemset.php?search=hpu