#P17933. Subgrid Connected Components

Subgrid Connected Components

Subgrid Connected Components

给定一个 (2N+1)×(2N+1)(2N+1)\times(2N+1) 的字符网格 SS。行列从 11 开始编号,字符满足:

  • 行号和列号均为奇数时,字符为 o;
  • 行号为奇数、列号为偶数时,字符为 - 或 .;
  • 行号为偶数、列号为奇数时,字符为 | 或 .;
  • 行号和列号均为偶数时,字符为 .。

共有 QQ 个独立询问,每个询问给出四个奇数 U,D,L,RU,D,L,R。考虑行范围 [U,D][U,D]、列范围 [L,R][L,R] 内的子网格,将所有 o 视为顶点,夹在两个相邻顶点中间的 - 或 | 视为无向边,求所得无向图的连通分量数。

更准确地说,顶点为 (x,y)(x,y),其中 x,yx,y 为奇数且 U≤x≤DU\le x\le D、L≤y≤RL\le y\le R。如果 y+2≤Ry+2\le R 且 Sx,y+1S_{x,y+1} 为 -,则连接 (x,y)(x,y) 与 (x,y+2)(x,y+2);如果 x+2≤Dx+2\le D 且 Sx+1,yS_{x+1,y} 为 |,则连接 (x,y)(x,y) 与 (x+2,y)(x+2,y)。除此之外没有其他边。

输入格式

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

每个 SiS_i 为长度 2N+12N+1 的字符串。

输出格式

输出 QQ 行,每行一个整数,为对应询问的连通分量数。

数据范围

1≤N≤20001\le N\le2000,1≤Q≤70001\le Q\le7000,1≤Ui≤Di≤2N+11\le U_i\le D_i\le2N+1,1≤Li≤Ri≤2N+11\le L_i\le R_i\le2N+1,询问的四个坐标均为奇数。网格保证符合上述字符规则。

原题内存限制为 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