分数: 700 点
问题陈述
Nuske 有一个网格 N 行和 M 方格列。行已编号 1 通过 N 从上到下,各列已编号 1 通过 M 从左到右。 网格中的每个方块都涂成蓝色或白色。如果 S_{i,j} is 1,位于 i第行和 j第列是蓝色的;如果 S_{i,j} is 0,正方形为白色。 对于每对两个蓝色方块 a 和 b,最多有一条路径从 a,重复前进到相邻(并排)的蓝色方块,最后到达 b,无需多次遍历同一个方块。
Phantom Thnook,Nuske 永远的对手,给予 Q 向 Nuske 询问。的 i-第一个查询由四个整数组成 x_{i,1}, y_{i,1}, x_{i,2} 和 y_{i,2} 并问他以下问题:当网格的矩形区域由(并包括) x_{i,1}第行, x_{i,2}第行, y_{i,1}第列和 y_{i,2}第-列被切掉,该区域中有多少个由蓝色方块组成的连通分量?
处理所有查询。
约束
- 1 ≤ N,M ≤ 2000
- 1 ≤ Q ≤ 200000
- S_{i,j} 是 0 or 1.
- S_{i,j} 满足语句中解释的条件。
- 1 ≤ x_{i,1} ≤ x_{i,2} ≤ N(1 ≤ i ≤ Q)
- 1 ≤ y_{i,1} ≤ y_{i,2} ≤ M(1 ≤ i ≤ Q)
输入
输入由标准输入按以下格式给出:
N M Q
S_{1,1}..S_{1,M}
:
S_{N,1}..S_{N,M}
x_{1,1} y_{i,1} x_{i,2} y_{i,2}
:
x_{Q,1} y_{Q,1} x_{Q,2} y_{Q,2}
输出
对于每个查询,打印该区域中由蓝色方块组成的连接组件的数量。
示例输入 1
3 4 4 1101 0110 1101 1 1 3 4 1 1 3 1 2 2 3 4 1 2 2 4
示例输出 1
3 2 2 2

在第一个查询中,指定了整个网格。由蓝色方块组成的三个分量,因此 3 。
在第二个查询中,指定了红框内的区域。有两个部分由蓝色方块组成,因此 应打印 2 。 请注意,原始网格中属于同一组件的方块可能属于不同的组件。
示例输入 2
5 5 6 11010 01110 10101 11101 01010 1 1 5 5 1 2 4 5 2 3 3 4 3 3 3 3 3 1 3 5 1 1 3 4
示例输出 2
3 2 1 1 3 2