跳马问题

题目：

洛谷 P1644 跳马问题

题目背景

在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……

题目描述

中国象棋半张棋盘如图1所示。马自左下角(0,0)向右上角（m，n）跳。规定只能往右跳，不准往左跳。比如图1中所示为一种跳行路线，并将路径总数打印出来。

输入输出格式

输入格式：

只有一行：两个数n，m

输出格式：

只有一个数：总方案数total。

输入输出样例

输入样例#1：

4 8

输出样例#1：

37

说明

所有数据：n，m<=18

#include <cstdio>
int n , m ,ans ;
int dx[4] = {1,2,2,1} ;
int dy[4] = {2,1,-1,-2} ;
void dfs(int x ,int y)
{
  if(x == m && y == n)
  {
    ans ++ ;
  }
  int i ;
  int tx = 0 ;
  int ty = 0 ;
  for (i = 0 ; i< 4 ;i++)
  {
    tx = x + dx[i] ;
    ty = y + dy[i] ;
    if(tx >m  || tx <0 || ty >n || ty<0)
    continue ;
    else
    {
      dfs(tx,ty);
    }

  }
  
}
int main()
{
  scanf("%d%d",&n,&m);
  dfs(0,0);
  printf("%d",ans);
  
  return 0 ;
}