#BZOJ3814. 简单回路
-
ID: 2377
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
简单回路
No submission language available for this problem.
题目描述
在一个有障碍点的 n 行 m 列的网格图中，我们用 (x,y) 来表示第 x 行第 y 列的格子。如果该网格图中的回路满足下面两个条件：
不经过任何一个障碍点
回路不自交
则我们称该回路为合法的简单回路。
现在有 Q 个询问，每次询问有多少条合法的简单回路经过了 (x,y) 与 (x+1,y) 之间的边。
输入格式
第一行输入三个非负整数 n, m，k，表示 n 行 m 列的网格图中有 k 个障碍点。
接下来 k 行，每行两个正整数x,y (1≤x≤n,1≤y≤m)，表示 (x,y) 为一个障碍点（可能重复）
接下来一个整数 Q，表示 Q 个询问。
接下来 Q 行，每行两个正整数 x,y (1≤x≤n−1,1≤y≤m)，询问有多少条合法的简单回路经过了格子 (x,y) 与 (x+1,y) 之间的边。
输出格式
输出 Q 行，每行对应一组询问。请将答案 mod(1000000000+7) 之后输出。
4 4 4
2 2
2 4
3 2
4 4
4
1 1
1 4
3 3
2 2
1
0
1
0
数据范围与约定
N<=1000
M<=6
K<=100
Q<=10000