http://acm.pku.edu.cn/JudgeOnline/problem?id=3731初看以为是DP，后来发现不满足无后效性的条件，不能DP。
其实这题是个计数问题，对于到达一个目标点的方法，可以按转弯次数分一下类，由于路线的方式是顺时针，这样必然导致目标点的左上右下四个方向的已走出的路径数依次增加，问题就转换为如何求每一类的方法数了。显然，这是个组合数，假设从目标点到某边界共有n个点的距离，而这n个点中已经走过了m条路径，则共有C(n, m)种方法，然后运用乘法原理和加法原理即可解决问题。
代码写得不好，那四个方向其实可以写成循环的……
1 #include <cstdio>
2
3 const int MOD = 100000007;
4 const int MAX_N = 2001;
5
6 int cas, n, m, x, y, cnt;
7 int l, r, u, d;
8 int c[MAX_N][MAX_N];
9 long long tmp;
10
11 void CalcComb() {
12 c[0][0] = c[1][0] = c[1][1] = 1;
13 for (int i = 2; i < MAX_N; ++i) {
14 c[i][0] = c[i][i] = 1;
15 for (int j = 1; j < i; ++j)
16 c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
17 }
18 }
19
20 int main() {
21 CalcComb();
22 for (scanf("%d", &cas); cas; --cas) {
23 scanf("%d%d%d%d", &n, &m, &x, &y);
24 if (!x) {
25 puts("1");
26 continue;
27 }
28 l = r = d = u = cnt = 0;
29 while (1) {
30 ++u;
31 tmp = 1;
32 tmp = tmp * c[x - 1][l] % MOD;
33 tmp = tmp * c[n - x][r] % MOD;
34 tmp = tmp * c[y][d] % MOD;
35 tmp = tmp * c[m - y][u - 1] % MOD;
36 cnt = (cnt + tmp) % MOD;
37 if (u == m - y + 1) break;
38 ++r;
39 tmp = 1;
40 tmp = tmp * c[x - 1][l] % MOD;
41 tmp = tmp * c[n - x][r - 1] % MOD;
42 tmp = tmp * c[y][d] % MOD;
43 tmp = tmp * c[m - y][u] % MOD;
44 cnt = (cnt + tmp) % MOD;
45 if (r == n - x + 1) break;
46 ++d;
47 tmp = 1;
48 tmp = tmp * c[x - 1][l] % MOD;
49 tmp = tmp * c[n - x][r] % MOD;
50 tmp = tmp * c[y][d - 1] % MOD;
51 tmp = tmp * c[m - y][u] % MOD;
52 cnt = (cnt + tmp) % MOD;
53 if (d == y + 1) break;
54 ++l;
55 tmp = 1;
56 tmp = tmp * c[x - 1][l - 1] % MOD;
57 tmp = tmp * c[n - x][r] % MOD;
58 tmp = tmp * c[y][d] % MOD;
59 tmp = tmp * c[m - y][u] % MOD;
60 cnt = (cnt + tmp) % MOD;
61 if (l == x) break;
62 }
63 printf("%d\n", cnt);
64 }
65 return 0;
66 }
67