#P11715. [清华集训 2014] 简单回路
[清华集训 2014] 简单回路
题目描述
在一个有障碍点的 行 列的网格图中,我们用 来表示第 行第 列的格子。如果该网格图中的回路满足下面两个条件:
- 不经过任何一个障碍点
- 回路不自交
则我们称该回路为合法的简单回路。
现在有 个询问,每次询问有多少条合法的简单回路经过了 与 之间的边。
输入格式
第一行输入三个非负整数 ,表示 行 列的网格图中有 个障碍点。
接下来 行,每行两个正整数 ,表示 为一个障碍点(可能重复)
接下来一个整数 ,表示 个询问。
接下来 行,每行两个正整数 ,询问有多少条合法的简单回路经过了格子 与 之间的边。
输出格式
输出 行,每行对应一组询问。请将答案 之后输出。
4 4 4
2 2
2 4
3 2
4 4
4
1 1
1 4
3 3
2 2
1
0
1
0
1000 2 10
426 2
595 2
665 1
447 2
604 2
202 1
26 1
79 1
291 2
6 2
10
932 1
857 2
31 1
458 1
793 1
691 1
438 1
404 1
541 1
872 2
18156
27456
235
1496
26496
8034
96
2373
4982
26496
提示
测试点编号 | ||||
---|---|---|---|---|