马走日 题解

【题目描述】

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

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

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

【样例输入】

5 9

【样例输出】

37

==================题解=================

      递归深搜。

      两个数组分别是｛1，1，2，2｝(控制纵坐标)和｛2，-2，1，-1｝（控制横坐标）用来控制马的走向，对于每个位置将此位置的两个坐标分别加上两个数组中的相同元素即可枚举可到达的四个位置，之后判断是否在棋盘范围中，若在，则传入横纵坐标进行递归，函数开头要判断是否到达了目标点。