P17429 [ICPC 2018 Xuzhou R] Rikka with Grid Graphs

二维网格图，也称方形网格图，是一个包含 $n m$ 个顶点的无向图，这些顶点对应于 $n \times m$ 网格中的所有格点。此处的一条边是对网格中一根长度为 1 的火柴棍的抽象描述，用于连接两个相邻格点。 现在，Rikka 给了你一个由不超过 $(2 n m - n - m)$ 条边构成的 $n \times m$ 网格图。她希望你计算该无向图的不同定向的方案数，使得定向后的图是一个没有有向环的有向图。 在本问题中，一个无向图的定向是指为每条边分配一个方向，从而将原图转化为一个有向图。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 60$），表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 6$），分别表示网格图中一列的顶点数和一行的顶点数。 接下来是 $(2 n - 1)$ 行，每行至多包含 $(2 m - 1)$ 个字符，用于描述该网格图。其中的奇数行包含网格顶点（由分开的加号（`+`）表示）以及零个或多个水平边，而偶数行包含零个或多个垂直边。具体而言，所有可能出现的顶点都会在输入中表示。每条连接相邻顶点的水平边用一个减号（`-`）表示，每条垂直边则用一个竖线（`|`）表示。表示边的字符会恰好置于对应顶点之间。其余所有字符均为空格字符。 注意，如果任何输入行可能包含末尾空格，这些空格将被省略。

对于每组测试数据，输出一行一个整数，表示给定网格图的有效定向数。

翻译由 DeepSeek V4 Pro 完成