1688--【USACO】Dairy Route

1688: 【USACO】Dairy Route


时间限制: 1.000 Sec  内存限制: 64 MB
提交: 16  解决: 8
[提交] [状态] [报告] [命题人:]

题目描述

Consider the 'map' below of Farmer John's milk delivery service. It has N (2 <= N <= 100) rows and M ( 2 <= M <= 80) columns.
             North
        . . . . . . . T
        . . . . . . C .
        . . . . C S . .
        . S . . C . S .
        D C . . S . . .
Farmer John delivers milk to his rural customers (denoted as 'C') as he travels from the dairy (denoted as 'D' and always located in the lower left hand corner) to the town (denoted as 'T' and always located in the upper right corner). He traverses roads on the square grid by moving either horizontally to the right or vertically toward the top, never diagonally. FJ never travels toward the left or toward the bottom of his map. Some roads are blocked by snow (denoted as 'S') which means FJ can not traverse that square. Write a program that cowculates the total number of different milk routes available from the dairy to the town. Two routes are different if they differ on any part of the path. FJ routes are always arranged so that all customers can be reached while moving north and east. The total number of different milk routes will fit in a 32-bit signed integer.

输入

* Line 1: Four integers: N, M, C (the number of customers, 1 <= C), and S (the number of snow drifts, 0 <= S) * Lines 2..C+1: Each line contains a pair of space separated integers that give, respectively, the row and column of a customer. The dairy is located in the lower left corner at (1,1). Customers will not be located at the dairy or in the town. * Lines C+2..C+S+1: If S > 0, each line contains a pair of space separated integers that give, respectively, the row and column of a snowdrift.

输出

A single integer that is the total number of different milk routes available for FJ to deliver his milk.

样例

输入  复制
5 8 4 4 1 2 2 5 3 5 4 7 1 5 2 2 2 7 3 6
输出  复制
4

提示

ABOUT SAMPLE OUTPUT: [Here are all four routes for the example input/output:
 . . . . . . . *   . . . . . . . *   . . . . . . * *   . . . . . . * *
 . . . . * * * *   . . . . * * * *   . . . . * * * .   . . . . * * * .
 . . . . * S . .   . . . . * S . .   . . . . * S . .   . . . . * S . .
 . S * * * . S .   . S . * * . S .   . S * * * . S .   . S . * * . S .
 * * * . S . . .   * * * * S . . .   * * * . S . . .   * * * * S . . .
]

来源/分类