网站注册页面,微分销系统哪个好,wordpress 首页文章数量,做企业官网好吗题目#xff1a;
P1644 跳马问题 - 洛谷 | 计算机科学教育新生态
题目背景
在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……
题目描述
中国象棋半张棋盘如图 1 所示。马自左下角 (0,0) 向右上角 (m,n) 跳。规定只能往右跳#xff0c;不准往左跳。比…
题目
P1644 跳马问题 - 洛谷 | 计算机科学教育新生态
题目背景
在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……
题目描述
中国象棋半张棋盘如图 1 所示。马自左下角 (0,0) 向右上角 (m,n) 跳。规定只能往右跳不准往左跳。比如图 1 中所示为一种跳行路线并将路径总数打印出来。 输入格式
只有一行两个数 nm。
输出格式
只有一个数总方案数 total。
输入输出样例
输入 #1复制
4 8
输出 #1复制
37
说明/提示
对于 100% 的数据n,m≤18
思路
题目求的是从0,0到m,n的所有方案和所以我们使用方向数组模拟马右跳用计数器计数处理好边界即可。
代码如下
#includeiostream
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;}
