#P17933. Subgrid Connected Components
Subgrid Connected Components
Subgrid Connected Components
给定一个 的字符网格 。行列从 开始编号,字符满足:
- 行号和列号均为奇数时,字符为
o; - 行号为奇数、列号为偶数时,字符为
-或.; - 行号为偶数、列号为奇数时,字符为
|或.; - 行号和列号均为偶数时,字符为
.。
共有 个独立询问,每个询问给出四个奇数 。考虑行范围 、列范围 内的子网格,将所有 o 视为顶点,夹在两个相邻顶点中间的 - 或 | 视为无向边,求所得无向图的连通分量数。
更准确地说,顶点为 ,其中 为奇数且 、。如果 且 为 -,则连接 与 ;如果 且 为 |,则连接 与 。除此之外没有其他边。
输入格式
N
S_1
S_2
...
S_{2N+1}
Q
U_1 D_1 L_1 R_1
...
U_Q D_Q L_Q R_Q
每个 为长度 的字符串。
输出格式
输出 行,每行一个整数,为对应询问的连通分量数。
数据范围
,,,,询问的四个坐标均为奇数。网格保证符合上述字符规则。
原题内存限制为 384 MiB。
样例 1
输入:
3
o-o-o-o
|.....|
o-o.o.o
|.|....
o-o.o-o
....|.|
o.o-o-o
12
3 5 1 7
1 1 1 1
1 3 1 3
1 3 1 7
1 1 1 1
1 1 1 7
1 7 1 1
1 7 1 7
3 5 3 5
3 5 3 7
3 7 3 7
5 7 3 5
输出:
4
1
1
2
1
1
2
4
3
4
4
2