题目详情题解（0）讨论（0）提交记录（0）

AT_agc015_c.[AGC015C] Nuske vs Phantom Thnook

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Nuske 现在有一个 N×M(N,M≤2000)N\times M(N,M\le 2000) 的矩阵 SS，若 Si,j=1S_{i,j}=1，那么该处为蓝色，否则为白色，保证所有蓝色格子构成的连通块都是树。

给出 Q(Q≤200000)Q(Q\le 200000) 次询问, 每次询问一个子矩阵中蓝色连通块的个数。

输入格式

第一行 三个整数 N,M,QN,M,Q。
接下来 NN 行对应矩阵 SS，每行一个长度为 MM 且只包含 0,10,1 的字符串。
接下来 QQ 行, 每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2 表示相应询问。

输出格式

共 QQ 行, 每行一个整数对应相应询问。

输入输出样例

  • 输入#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

  • 输入#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

输入解题思路，AI测评打分。不知道怎么写?

首页