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 閱讀(323)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc