【郑轻】[1894]985的方格难题

问题描述

985的方格难题

时间限制：1 Sec内存限制：128 MB

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

Sample Output

问题分析

解法一：考虑dp，dp[i][j]表示到达位置（i，j）的方案数，
dp[i][j] = -1 表明该位置未被访问，直接暴力转移就可以啦。
时间复杂度：O(T * n * n)。

解法二：抛开坏的位置不说，发现从（1，1）到达每个位置的方案数都是杨辉三角里面的某个组合数。
而且达到位置(n, m)的方案数是C(n + m - 2，m - 1)。
记ans[1][1][n][m]为（1，1）到（n，m）的方案数。
这样结果就是ans[1][1][n][n] - ans[1][1][x][y] * ans[x][y][n][n]。防止出错，要用逆元。
时间复杂度：O(T * log(1e9 + 5)^4)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
int map[32][32];
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int n,x,y;
		scanf("%d %d %d",&n,&x,&y);
		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)
						if(j==1)
							map[i][j]=1;
						else
							map[i][j]=map[i][j-1];
					else if(j==1)
						map[i][j]=map[i-1][j];
					else
						map[i][j]=(map[i-1][j]+map[i][j-1])%1000000007;
				}
			}
		}
		printf("%d\n",map[n][n]==0?-1:map[n][n]);
	}
	return 0;
}

题目地址:【郑轻】[1894]985的方格难题