← 返回题目列表

AtCoder · agc015_c

C. 努斯克 vs 幻影特努克

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

分数: 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