grids 3741 Escape
http://poj.grids.cn/problem?id=3741
此题我用组合数学过的. 欢迎交流各种方法.
原题意: 从(0,0)开始,初始面向y轴正方向,只能右转或直走,每个格子至多经过1次,到达(x,y),求有多少种走法
转化为: 从(x,y)开始,初始朝向任意,只能左转或直走,!@#%^$#$^^$@%,到达(0,0)的走法数
总的走法数即为初始朝向分别为上下左右的走法数之和.
观察符合要求的路径,其肯定是螺旋形的,也就是各边不相交.
所以可以分别设 (x,y)上方横线数up, 下方横线数down, 左侧竖线数left, 右侧竖线数right
按初始朝向分4种情况,可以找出up,down,left,right之间的数量关系! 可以自己画一下,很容易发现.
以初始朝向左为例,求 S左:
left-1 = up = right = down (令其 = k)
这样对某个k ,走法数即为在4个方位取出对应数量线段的方法数.
设(x,y)到地图4个边界的距离分别为 dl, du, dr, dd
则 Sk = C(left-1, dl-1) * C(up, du) * C(right, dr) * C(down, dd)
其中left项的上下标都减了1,是因为左侧竖线肯定有一条是y轴,所以只选出剩下的left-1条
枚举所有不会越界的 k ,即保证 C(k, n) 中 k<=n, 就求得这个方向方法数之和
最后把4个方向的S加起来即可
注意一些特殊情况:
1. (x,y)在 y 轴上时,直接输出1
2. 初始方向为下的情况,枚举k要从1开始,也就是至少要绕一圈. 因为 !%!@^$#$@#$ :)
ps.
初始朝向 上: left-1 = up-1 = right = down
初始朝向 右: left-1 = up-1 = right-1 = down
初始朝向 下: left = up = right = down
代码:
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 const __int64 MOD = 100000007;
8 __int64 x,y,X,Y,c[2100][2100];
9 __int64 ans,tmp;
10 int dk[4][4] = {//lurd
11 1,0,0,0, //left
12 1,1,0,0, //up
13 1,1,1,0, //right
14 1,1,1,1 //down
15 };
16 int N;
17
18 __int64 func(__int64 n, __int64 k){
19 if(n<k) return 0;
20 if(c[n][k]<0)
21 c[n][k] = (func(n-1, k-1) + func(n-1, k)) % MOD;
22 return c[n][k];
23 }
24
25 inline int mi4(int x1, int x2, int x3, int x4){
26 return min(min(x1,x2),min(x3,x4));
27 }
28
29 int main(){
30 int i,j,k,z;
31 int left,right,up,down;
32 memset(c, 0xff, sizeof(c));
33 c[0][0] = 1;
34 for(i=1; i<=2000; i++){
35 c[i][0] = 1;
36 c[i][1] = i;
37 c[i][i] = 1;
38 }
39 scanf("%d",&N);
40 while(N--){
41 scanf("%I64d %I64d %I64d %I64d",&X, &Y, &x, &y);
42 left = x; right = X-x;
43 up = Y-y; down = y;
44 if(x == 0){
45 printf("1\n");
46 continue;
47 }
48 ans = 0;
49 for(i=0; i<4; i++){
50 z = mi4(left-dk[i][0], up-dk[i][1], right-dk[i][2], down-dk[i][3]);
51 for(k=0; k<=z; k++){
52 tmp = func(left-1, k+dk[i][0]-1) % MOD;
53 tmp = (tmp * func(up, k+dk[i][1])) % MOD;
54 tmp = (tmp * func(right, k+dk[i][2])) % MOD;
55 tmp = (tmp * func(down, k+dk[i][3])) % MOD;
56 ans = (ans + tmp) % MOD;
57 }
58 }
59 printf("%I64d\n",ans);
60 }
61 return 0;
62 }
63
posted on 2009-05-18 18:33
wolf5x 阅读(314)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc