Collecting Items
Time limit2sMemory limit128 MB
Count monotone right/up paths from bottom-left to top-right on a grid that must pass through every item cell and avoid obstacle cells.
- Level
Medium6 of 10
- Topics
- Combinatorics, Dynamic programming, Math
- Solved
- No attempts yet
Problem
An N × M grid map contains items and obstacles. The starting cell is the bottom-left cell (1, 1), and the destination is the top-right cell (N, M).
Each move goes exactly one cell to the right or one cell upward. You cannot pass through a cell that contains an obstacle. Before reaching the destination, you must collect every item on the map.
Find the number of movement paths that satisfy these conditions.
Input
The first line contains four integers N, M, A, and B. N and M are the width and height of the grid, respectively, and 1 ≤ N, M ≤ 100. A is the number of items, with A ≥ 1. B is the number of obstacles, with B ≥ 0.
Each of the next A lines contains the position of one item. Each of the following B lines contains the position of one obstacle. Each position is given as two integers x and y; the bottom-left cell is (1, 1), and the top-right cell is (N, M).
Output
Print the number of movement paths that satisfy the conditions on the first line. The answer fits in the range of int.