跳马问题

【问题描述】

有一只中国象棋中的 “ 马 ” ，在半张棋盘的左上角出发，向右下角跳去。规定只许向右跳（可上，可下，但不允许向左跳）。请编程求从起点 A(1,1) 到终点 B(m,n) 共有多少种不同跳法。

【输入格式】

输入文件只有一行，两个整数m和n（1≤m,n≤20），两个数之间有一个空格。

【输出格式】

输出文件只有一个整数，即从 A 到 B 全部的走法。

【输入输出样例】

输入文件(horse.in)

5　9

输出文件(horse.out)

很简单的dp。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdlib>
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 using namespace std;
 6  ifstream fin("horse.in");
 7 ofstream fout("horse.out"); 
 8 int he=0,zo=0;
 9 int heng[4]={-2,-1,1,2};
10 int zong[4]={1,2,2,1};
11 int jiyi[25][25]={0}; 
12 int dp(int hen,int zon){
13  if(hen>he||zon>zo)return 0;
14  if(hen<1)return 0;
15  if(jiyi[hen][zon]!=0)return jiyi[hen][zon];
16  if(hen==he&&zon==zo)return 1;
17  int tem=0;
18  for(int x=0;x<4;x++){
19   tem+=dp(hen+heng[x],zon+zong[x]);
20 　} 
21 　jiyi[hen][zon]=tem;
22  return tem;
23 } 
24 
25 int main(int argc, char *argv[]) {
26  fin>>he>>zo;
27  int ans=dp(1,1);
28  fout<<ans;
29  return 0;
30 }