← 返回题目列表

AtCoder · stpc2025_1_i

I. 子电网连接组件

中文机器翻译题面 查看原题

配点 : 100 点

注意

此问题的内存限制为 384 MiB。 您将获得一个由

問題文

2N+1 行 2N+1 列组成的网格。在这里, N 是正整数。从网格上方 i 第几行,从左边开始 j 柱方 (1 \le i, j \le 2N + 1) 只需将其移至 (i, j) 。鳟鱼 (i, j) 是一个字符 S_{i,j} 被写入并满足以下属性。

  • i 是奇数, 当 j 为奇数时, 当 S_{i, j} = o
  • i 是奇数, 当 j 为偶数时, S_{i, j} = - 或 至少 .
  • i 是偶数, j 为奇数时, 当 S_{i, j} = | 或 至少 .
  • i 是偶数, j 为偶数时, S_{i, j} = .

独立查询 给出了 Q 。 i 個目 (1 \le i \le N) 时,奇数 鉴于 U_i, D_i, L_i, R_i (1 \le U_i \le D_i \le 2N+1,\ 1 \le L_i \le R_i \le 2N+1) ,请回答以下问题。

部分网格 在 [U_i, D_i] \times [L_i, R_i] 中,字符 o 作为顶点、字符 求 - 和 按字典顺序比较 | 为边时无向图的连通分量数。

具体回答以下问题。

((D_i - U_i + 2) / 2) \times ((R_i - L_i + 2) / 2) 顶点无向图 创建 G 和顶点是 小于或等于 U_i 以上 D_i 的奇数 x 和 按字典顺序比较 L_i 以上 R_i 的奇数 y 对 假设用 (x, y) 表示。另外,无向图 G 具有以下无向边并且没有其他无向边。 如果满足

  • 奇数 x, y 是 在 U_i \le x \le D_i,\ L_i \le y \le R_i - 2 和 S_{x,y+1} = - ,则顶点 (x, y) 与 边 (x, y+2) 之间有一条无向边。
  • 奇数 x, y 是 在 U_i \le x \le D_i - 2,\ L_i \le y \le R_i 和 S_{x+1,y} = | ,则顶点 (x, y) 与 边 (x+2, y) 之间有一条无向边。

无向图 求 G 的连通分量的数量。

制約

  • N 是一个整数
  • 1 \le N \le 2000
  • i 是奇数, 当j 为奇数时, 当 S_{i, j} = o
  • i 是奇数, 当j 为偶数时, S_{i, j} = - 或 至少 .
  • i 是偶数,j 为奇数时, 当 S_{i, j} = | 或 至少 .
  • i 是偶数,j 为偶数时, S_{i, j} = .
  • Q 是一个整数
  • 1 \le Q \le 7000
  • 1 \le U_i \le D_i \le 2N+1
  • 1 \le L_i \le R_i \le 2N+1
  • U_i, D_i, L_i, R_i 是奇数

入力

输入是按以下格式从标准输入给出的。

N
S_{1,1}S_{1,2}\cdotsS_{1,2N+1}
S_{2,1}S_{2,2}\cdotsS_{2,2N+1}
\vdots
S_{2N+1,1}S_{2N+1,2}\cdotsS_{2N+1,2N+1}
Q
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_Q D_Q L_Q R_Q

出力

Q 行。 i=1,2,\dots, Q 关于 i 在线 i 个查询的答案。


入力例 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

出力例 1

4
1
1
2
1
1
2
4
3
4
4
2

给定的网格如下所示: 第

1 个查询的答案如下图所示。 4 。 对于