【C语言】湖上的冰精
出题× 整活√
题目描述:
位于湖面坐标原点处的灵梦想去找在湖面另一点的魔理沙,她每次可以沿平行坐标轴的方向走一个单位长度。因为灵梦急死了,所以她只想走最快的路线。同时,在另外某处琪露诺和大妖精在玩耍,琪露诺会向周围随机丢出冰块,冰块的落点与她的距离位于开区间(2,3)内,且落点的坐标均为整数。灵梦想知道能保证自己不被冰块砸中且最快的路线有多少种。(灵梦在路上可以经过琪露诺所在的点)
输入格式:
两行,第一行为魔理沙的坐标,第二行为琪露诺的坐标。均为整数。
输出格式:
一个整数,表示灵梦可以选择的路线方案数,若不存在请输出0。
样例输入:
6 7
3 2
样例输出:
49
数据范围:
均为整数且位于闭区间[0,20]内。
提示:
可分别尝试使用递归写法和递推(循环)写法,若递归写法超时可尝试使用记忆化搜索避免重复遍历。
——by sakurara
测试用例:
测试输入 | 测试输出 |
6 7
3 2 |
49
|
7 8
4 4 |
140
|
3 8
4 14 |
165
|
10 13
5 7 |
60424
|
9 14
2 0 |
66708
|
17 16
5 18 |
密
|
16 18
15 11 |
密
|
16 20
9 7 |
密
|
17 17
2 1 |
密
|
20 20
9 12 |
密
|