P16514 [GKS 2015 #D] Dynamic Grid

我们有一个 $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 \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 完成