CF2247F Paths on a Grid

给定一个大小为 $n \times m$ 的网格 $a$。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。网格中的每个格子要么被阻塞，要么是自由的。格子 $(1, 1)$ 和 $(n, m)$ 都是自由的。 对于网格 $a$，一个格子的集合 $S$（$S$ 可以包含被阻塞的格子）被称作“好”的，需满足以下条件： - $S$ 非空； - 对于 $S$ 中的每个格子 $(i, j)$，从 $(1, 1)$ 到 $(n, m)$ 的所有只经过自由单元格、每步只能向下或向右移动，并且经过格子 $(i, j)$ 的路径，必然也经过 $S$ 中的所有其它格子。 请计算网格 $a$ 的好格子集合的数量，输出对 $998\,244\,353$ 取模的结果。

每组测试数据包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。 接下来每组测试用例，第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^6$）。 接下来的 $n$ 行中，每行包含一个长度为 $m$ 的字符串 $a_{i, 1} a_{i, 2} \ldots a_{i, m}$（$a_{i, j} \in \{0, 1\}$），表示网格的第 $i$ 行。如果 $a_{i, j} = 1$，则格子 $(i, j)$ 是自由的；否则被阻塞。保证 $a_{1, 1} = a_{n, m} = 1$。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行一个整数，为满足条件的好集合的数量对 $998\,244\,353$ 取模的结果。

在第一个样例中，唯一的非空格子集合是 $\{(1, 1)\}$，它是好的。因此答案为 $1$。 在第三个样例中，不存在只经过自由格子的 $(1, 1)$ 到 $(2, 2)$ 的路径。因此每个非空的格子集合都是好的，所以答案是 $2^4 - 1 = 15$。 在第五个样例中，集合 $\{(2, 2), (3, 2)\}$ 是好的，因为每条从 $(1, 1)$ 到 $(4, 4)$、只经过自由单元格且经过这两个格子的路径，必然两个格子都经过。但是集合 $\{(3, 3), (4, 3)\}$ 不是好的，因为路径 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$ 只经过 $(3, 3)$，没有经过 $(4, 3)$。可以证明总的好集合数是 $162$。 由 ChatGPT 5 翻译