洛谷 P1644 跳马问题 C语言
题目：
P1644 跳马问题 - 洛谷 | 计算机科学教育新生态
题目背景
在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……
题目描述
中国象棋半张棋盘如图 1 所示。马自左下角 (0,0) 向右上角 (m,n) 跳。规定只能往右跳，不准往左跳。比如图 1 中所示为一种跳行路线，并将路径总数打印出来。
输入格式
只有一行：两个数 n，m。
输出格式
只有一个数：总方案数 total。
输入输出样例
输入 #1复制
4 8
输出 #1复制
37
说明/提示
对于 100% 的数据：n,m≤18
思路：
题目求的是从（0,0）到（m,n）的所有方案和，所以我们使用方向数组模拟马右跳，用计数器计数，处理好边界即可。
代码如下：
#include<iostream>
using namespace std;
typedef long long ll;
int cnt = 0;
int dx[] = {1,2,2,1};//长
int dy[] = {2,1,-1,-2};//宽
int n,m;
void dfs(int x,int y)
{
if(x == m && y == n)
{
cnt++;
return;
}
for(int i = 0 ; i < 4 ; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if(tx >= 0 && tx <= m && ty >= 0 && ty <= n)
dfs(tx,ty);
}
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
dfs(0,0);
cout << cnt << '\n';
return 0;
}