洛谷 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;}