CF1864D Matrix Cascade

有一个大小为 $n \times n$ 的矩阵，矩阵中的元素只包含 $0$ 和 $1$。行号从上到下为 $1$ 到 $n$，列号从左到右为 $1$ 到 $n$。第 $x$ 行第 $y$ 列的单元格记作 $(x, y)$。 AquaMoon 想要将矩阵中的所有元素都变为 $0$。每一步她可以进行如下操作： - 选择任意一个单元格，记为 $(i, j)$，然后翻转 $(i, j)$ 处的元素，并且还要翻转所有满足 $x > i$ 且 $x - i \ge |y - j|$ 的单元格 $(x, y)$。翻转的意思是将 $0$ 变为 $1$，$1$ 变为 $0$。 请你帮助 AquaMoon 计算，将所有元素都变为 $0$ 至少需要多少步。可以证明一定存在解。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 3000$）。 接下来的 $n$ 行，每行是一个长度为 $n$ 的仅包含 $0$ 和 $1$ 的二进制字符串，表示矩阵的一行。 保证所有测试用例的 $n^2$ 之和不超过 $9\,000\,000$。

对于每个测试用例，输出一个整数，表示最少需要多少步。

在第一个测试用例中，可以按如下方案操作： 1. 对单元格 $(1, 3)$ 执行操作。 显然，初始矩阵中元素不全为 $0$，所以至少需要一次操作。因此答案为 $1$。 在第二个测试用例中，可以按如下方案操作： 1. 对单元格 $(3, 3)$ 执行操作； 2. 对单元格 $(1, 1)$ 执行操作。 可以证明无法在 $0$ 步或 $1$ 步内将所有元素变为 $0$，所以答案恰好是 $2$。 由 ChatGPT 4.1 翻译