#P17619. Gracemeria Patrol
Gracemeria Patrol
1.5s 512M
题目描述
给定一个 的 01 矩阵,每一次操作可以改变一个位置以及其上面、左边、右边的值。如果原值是 ,则改变之后变成 ;否则变成 。
例如下面矩阵在改变中括号表明的位置之后的形态:
$$\begin{bmatrix}0&1&0&1&1\\1&0&[0]&1&0\\0&0&0&0&1\end{bmatrix}\rightarrow \begin{bmatrix}0&1&1&1&1\\1&1&1&0&0\\0&0&0&0&1\end{bmatrix}$$特别的,如果操作点在边界上,那么仅改变未超出边界的部分。
现给定 组询问,每组询问一个区间 和一个常数 ,请你对行号在 内的 01 子矩阵求出通过选出一些位置进行一次操作使其变为全 的方案中,第 行被操作了几次。
特别的,如果没有或者有多种选择操作位置的方法,输出 。
询问之间相互独立。
输入格式
第一行三个整数 。
接下来 行,每行 个字符,给出 01 矩阵。
接下来 行,每行三个整数表示询问的 。
输出格式
行,每行一个整数表示对应询问的答案。
输入输出样例 #1
输入 #1
10 4 2
1010
0110
0101
0000
1011
0111
1110
1011
0001
1100
1 10 6
2 5 3
输出 #1
2
2
说明/提示
- Subtask 1(10 pts):。
- Subtask 2(20 pts):。
- Subtask 3(20 pts):。
- Subtask 4(20 pts):。
- Subtask 5(30 pts):无特殊限制。
对于 的数据,满足 ,,,。