题目描述

声明：本题为原题转载及翻译，若侵犯了您的合法权益，请与本站联系，我们将删除题目。

原题链接

Nuske 有一个 $N$ 行 $M$ 列的方形网格。行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。网格中的每个单元格都涂成蓝色或白色。如果 $S_{i,j}=1$，则第 $i$ 行第 $j$ 列的单元格为蓝色；如果 $S_{i,j}=0$，则单元格为白色。对于每对蓝色单元格 $a$ 和 $b$，最多存在一条每步移动到相邻（有公共边）的蓝色单元格，且不重复经过同一个单元格的，从 $a$ 开始到达 $b$ 的路径。

Nuske 永恒的对手 Phantom Thnook 向 Nuske 发出了 $Q$ 次查询。第 $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}$ 列的部分，在该区域有几个由蓝色单元格组成的四联通块？

请你回答所有查询。

输入格式

输入从标准输入流按以下形式给出：

$N$　$M$　$Q$
$S_{1,1} \cdots S_{1,M}$
$\vdots$
$S_{N,1} \cdots S_{N,M}$
$x_{1,1}$　$y_{1,1}$　$x_{1,2}$　$y_{1,2}$
$\vdots$
$x_{Q,1}$　$y_{Q,1}$　$x_{Q,2}$　$y_{Q,2}$

输出格式

对于每个询问，输出一行一个整数表示该区域内由蓝色单元格组成的四联通块个数。

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

3
2
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

3
2
1
1
3
2

数据范围与提示

对于所有数据：

• $1\le N,M\le 2000$
• $1\le Q\le 200000$
• $S_{i,j}\in \{0,1\}$，且满足题目条件
• $1\le x_{i,1}\le x_{i,2}\le N(1\le i\le Q)$
• $1\le y_{i,1}\le y_{i,2}\le M(1\le i\le Q)$