1 2 3 4 5 6 7 8
A +---+---+---o---+---o---+---+----+--------->Y
| | | | | | | | |
1 +---+---o---+---+---+---o---+----+
| | | | | | | | |
2 +---+---+---+---C---+---+---+----+
| | | | | | | | |
3 +---+---o---+---+---+---o---+----+
| | | | | | | | |
4 +---+---+---o---+---o---+---+----+ B(4,8)
|
|
V
X
6 6 3 2
17
大意：从起点开始到终点进行DP
#include<cstdio> #include<cstring> using namespace std; int n,m,x,y; long long dp[50][50]; int main() { int i,j; while(~scanf("%d%d%d%d",&m,&n,&x,&y)) { for(int i = 0 ; i <= m+1;i++) for(int j = 0 ; j <= n+1;j++) dp[i][j] = 0; dp[x-2+1][y-1+1] = dp[x-2+1][y+1+1] = dp[x+1][y+1] = dp[x-1+1][y-2+1] = dp[x-1+1][y+2+1] = dp[x+1+1][y+2+1] = dp[x+1+1][y-2+1] = dp[x+2+1][y+1+1] = dp[x+2+1][y-1+1] = -1; dp[1][1] = 1; for(int i = 1; i <= m + 1;i++) for(int j =1 ;j <= n +1 ;j++) { if(dp[i][j] == -1) continue; dp[i][j] += dp[i-1][j] + dp[i][j-1]; if(dp[i-1][j] == -1) dp[i][j]++; if(dp[i][j-1] == -1) dp[i][j]++; } printf("%lld\n",dp[m+1][n+1]); } return 0; }
原文：http://www.cnblogs.com/zero-begin/p/4374437.html
