【问题描述】
有一只中国象棋中的“ 马” ，在半张棋盘的左上角出发，向右下角跳去。
规定只许向右跳（可上，可下， 但不允许向左跳）。请编程求从起点A(1,1)到终点B(m,n) 共有多少种不同跳法。
【输入格式】
输入文件只有一行，两个整数m 和n（1≤m,n≤20），两个数之间有一个空格。
【输出格式】
输出文件只有一个整数，即从A 到B 全部的走法。
【输入输出样例】
输入文件(horse.in)
5 9
输出文件(horse.out)
37
经典的 dfs 板子题，不做解释。
***然后我被坑了：我以为棋盘大小就是一般的象棋棋盘那么大，然后数组也就开了那么大，GG了……………………
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 #define rep(i, a, n) for(int i = a; i <= n; ++i) 9 #define per(i, n, a) for(int i = n; i >= a; --i) 10 int m, n, tot = 0; 11 int dx[10] = {0, -2, -1, 1, 2}, dy[10] = {0, 1, 2, 2, 1}; 12 bool a[25][25]; 13 void dfs(int x, int y) 14 { 15 if(x == m && y == n) {tot++; return;} 16 rep(i, 1, 4) 17 { 18 int newx = x + dx[i], newy = y + dy[i]; 19 if(newx > 0 && newx <= m && newy > 0 && newy <= n && !a[newx][newy]) 20 { 21 a[newx][newy] = 1; 22 dfs(newx, newy); 23 a[newx][newy] = 0; 24 } 25 } 26 } 27 int main() 28 { 29 freopen("horse.in", "r", stdin); 30 freopen("horse.out", "w", stdout); 31 scanf("%d%d", &m, &n); 32 dfs(1, 1); 33 printf("%d\n", tot); 34 return 0; 35 }