| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1275
RG的故事
Time Limit: 1000ms
Memory Limit: 65536kb Description
USTC的Robot Game(RG)一直都是ustcer非常喜欢的一个课外活动。现在玩RG活动的同学们遇到了一个问题：有如下图所示的一块平面板(分成了N行M列)，假设机器人总是从最左下角(0,0)出发，朝最右上角(M,N)走去。但是某些路设有障碍，机器人不能通过(图中的AB,CD,EF,HG为不能通过的路径)，所以机器人必须绕过这些路而走其他的路。 现在的问题是求出机器人从起点(0，0)到终点(M,N)能走的不同的路径总数。 注意：机器人每次只能向上或向右走一步。 
Input
第一行输入一个数T(T<=10)，代表下面将有T组测试数据。每组测试数据包括两部分：第一部分：四个正整数N,M,K,P(0<N,M<=10000,0<=K<=10,P为小于400的奇素数)，N,M,K分别代表该平面板的行数、列数以及不能通过的路径的条数。 第二部分：K行，每行包括4个整数x1,y1,x2,y2。坐标点(x1,y1)、(x2,y2)分别代表每条路的顶点坐标，其中x1=x2或y1=y2。 数据保证所有不能通行路径都在此平面网格范围内，且没有任何两条路径完全相同，且不能通行路径的长度都为单位长度。 Output
针对每组测试数据，输出相应的路径数，如果该值大于等于P，则输出对P取模后的余数。
Sample Input
2 5 10 4 97 2 2 3 2 4 2 5 2 6 2 6 3 7 2 7 3 2 3 0 97 Sample Output
16 10 |