#2142. [NOIP1997 提高组] 骑士游历

[NOIP1997 提高组] 骑士游历

说明

设有一个nn *m m的棋盘。

如下图,在棋盘上任一点有一个中国象棋马

马走的规则为:

1)马只能走日字

2)马只能向右跳

如下图

问给定起点x1,y1x_1,y_1和终点x2,y2x_2,y_2,求出马从x1,y1x_1,y_1出发到x2,y2x_2,y_2的合法路径条数

例如:(nn=10,mm=10),起点(1,5),终点(3,5),应输出2(由(1,5)到(3,5)共有2条路径,如下图:

输入格式

一行6个整数n,m,x1,y1,x2,y2n,m,x_1,y_1,x_2,y_2

输出格式

输出方案数

样例

30 30 1 15 3 15
2

数据范围与提示

2n,m502\leqslant n,m\leqslant 50