题目描述

我们有一个 $R$ 行 $C$ 列的网格，其中每个格子的值要么是 $0$，要么是 $1$。我们将在该网格上执行 $N$ 次操作，每次操作是以下两种之一：

• 操作 M：将网格中某一格子的数字改为 $0$ 或 $1$。
• 操作 Q：求出由 $1$ 构成的不同连通区域的个数。一个由 $1$ 构成的连通区域是指一个全为 $1$ 的格子子集，其中该区域内的任意一个格子都可以通过沿着边（而非角）在格子间移动，到达该区域内的任意其他格子。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例首先是一行包含两个整数 $R$ 和 $C$，表示网格的行数和列数。然后有 $R$ 行，每行包含 $C$ 个字符，每个字符要么是 0，要么是 1。这些行表示网格的初始状态。

接下来一行包含一个整数 $N$，表示要在网格上执行的操作次数。再接下来的 $N$ 行，每行描述一次操作。所有操作 M 的格式均为 M x y z，表示将第 $x$ 行第 $y$ 列的格子改为值 $z$。所有操作 Q 的格式均为 Q。

输出格式

对于每个测试用例，首先输出一行 Case #x:，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后，对于该测试用例中的每一个操作 Q，按其出现顺序，输出一行包含当前由 $1$ 构成的连通区域的数量。

1
4 4
0101
0010
0100
1111 7
Q
M 0 2 1 
Q
M 2 2 0 
Q
M 2 1 0 
Q

Case #1: 
4
2
2
2

提示

限制

• $1 \le T \le 10$。
• $1 \le R, C \le 100$。
• $0 \le x < R$。
• $0 \le y < C$。
• $0 \le z \le 1$。

小数据集（测试集 1 - 可见）

• $1 \le N \le 10$。

大数据集（测试集 2 - 隐藏）

• $1 \le N \le 1000$。

翻译由 DeepSeek V4 Pro 完成