405622: GYM102012 L Rikka with Grid Graphs

A two-dimensional grid graph, also known as a square grid graph, is an undirected graph with $$$n m$$$ vertices corresponding all nodes in a $$$n \times m$$$ grid. An edge here is an abstract description for a matchstick of length one in the grid connecting two adjacent nodes.

Now, Rikka gives you a $$$n \times m$$$ grid graph made with no more than $$$(2 n m - n - m)$$$ edges. She wants you to calculate the number of different orientations for the undirected graph such that the oriented graph is a directed graph with no directed cycles.

In this problem, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 60$$$), the number of test cases.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 6$$$), the number of vertices in one column and one row of the grid graph respectively.

Then $$$(2 n - 1)$$$ lines follow, each of which has at most $$$(2 m - 1)$$$ characters, describing the grid graph. The odd lines of them contain grid vertices, represented by separated plus signs ('+'), and zero or more horizontal edges, while the even lines of them contain zero or more vertical edges. Specifically, all possible vertices are represented in the input. Each horizontal edge connecting neighbouring vertices is represented by a single minus sign ('-'), while each vertical edge is represented by a single vertical bar ('|'). The edge characters will be placed exactly between the corresponding vertices. All other characters will be space characters.

Note that if any input line could contain trailing whitespace, that whitespace will be omitted.

For each test case, output a single line with a single integer, the number of valid orientations for the given grid graph.

4
2 2
+-+

+ +
2 2
+-+
|
+ +
2 2
+-+
|
+-+
2 2
+-+
| |
+-+

2
4
8
14