/ C++党 / 题库 /

[noip1997]路径数目

[noip1997]路径数目

时间限制:1s 空间限制:1024KiB


题目来源

本题是1997年提高组的第四题(难度:普及+/提高-),希望你能把它做出来,加油!!!^_^

题目描述

小P在和小Q下中国象棋的时候,提出了一个很有趣的问题。
设有一个nm的棋盘,在棋盘上(x1,y1)处有一个中国象棋马,现在马要走到(x2,y2)去(至于为什么,我也不知道)。(注意:本题中所给出的均为平面直角坐标系中的坐标,即先列再行)
在这里定义马走的规则为:
1.马走日字;
2.马只能向右走。
现在小P和小Q想知道到底有多少条路径可以让马从(x1,y1)走到(x2,y2),但是这个棋盘实在是太大了,所以小P和小Q想找学习信奥的你帮忙。

输入输出格式

输入格式:

输入6个正整数n、m、x1、y1、x2、y2,n、m表示棋盘的大小,x1、y1、x2、y2分别表示马的起始坐标和马的终止坐标。

输出格式:

一个正整数,表示路径的数目,若不存在路径,则输出“0”(双引号不用输出)。

输入输出样例

Input #1

10 10 1 5 3 5

Output #1

2

时间和空间限制

每个测试点时间1s,空间1024KiB。

数据范围约定

100%的数据保证1≤n,m≤50,1≤x1,x2≤n,1≤y1,y2≤m。

提供者

Vijos 梁忆炎

信息

难度
6
分类
动态规划 | 记忆化搜索 点击显示
标签
递交数
3
已通过
2
通过率
67%
上传者