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