问题 22344 --过河卒(NOIP2002)

22344: 过河卒(NOIP2002)

时间限制: 1 Sec  内存限制: 128 MB
提交: 11  解决: 11
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述

如下图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图中C 点上的马可以控制 9 个点(图中除A,B之外的黑点)。卒不能通过对方马的控制点。


棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 100 的整数,同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入

B点的坐标(n,m)以及对方马的坐标(x,y)

输出

一个整数(路径的条数)。

样例输入

6 6 3 2

样例输出

17

提示


设二维数组a[i,j]表示从A点走到第i行第j列位置的路径条数。按题意,过河卒只能向下、或者向右行走。



(1).观察图中行坐标轴和列坐标轴上点的路径条数,则:a[i,0]=1,a[0,j]=1



(2).对于没被马控制的坐标点,如图中[1,1]点,只能从[0,1]和[1,0]走到[1,1]点,则:



    a[1,1] = a[1,0]+a[0,1] = 2



同理:任意一个没被马控制的坐标点[i,j],只能从[i-1,j]和[i,j-1]走到[1,1]点,则:



    a[ i,j ]=a[i-1,j]+a[i,j-1]



(3).对于被马控制的坐标点,则:a[i , j] = 0



那么,对于已知马点坐标 [ i , j ] ,如何标识被马控制的坐标点呢?










   dx[1..8]=
(2,1,-1,-2,-2,-1,1,2)



   dy[1..8]=
(1,2,2,1,-1,-2,-2,-1)



已知马点坐标 [x,y],求得被马控制点的坐标为:



x = x + dx    y =
y + dy

来源

[提交][状态]