设有一个N*M(1≤ N≤50, 1≤ M≤ 50)的街道(如下图):
规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
如下为N=3,M=3的街道图,从A出发到达B共有6条可供行走的路径:
若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用“*”表示的部分。
此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2,2), (8,4),此时从A出发到达B的路径仅有两条。
程序要求:
任务一:给出N,M后,求出所有从A出发到达B的路径的条数。
任务二:给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标 (X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。
N M
障碍区域两对顶点坐标(若无障碍区则该行无输入)。
若未给出障碍区域顶点坐标,输出任务一答案,否则输出任务二答案。