Problem G
Tree in a Grid
Input: Standard Input
Output: Standard Output
You are given a grid of row r and column c. The rows are numbered from 0 to r-1 and columns are numbered from 0 to c-1. A node in row i and column j can have edge with nodes at position (i-1,j),(i,j-1),(i+1,j) and (i,j+1). Now for the given grid some of its edge is given. You can add some other edge in the grid. You have to add the edges in such a way so that all the nodes in the grid are connected but do not create any cycle. You have to count the number of ways that you can add edges in the grid.
First line contains T(1≤T≤30) the number of test cases. Then T test cases follow.
First line of each test case contain 3 integer r(1≤r≤200),c(1≤c≤8) and md(1≤md≤1000000). Next 2*r-1 line contains the description of the maze. Each of these line contains 2*c-1 character. Each of the even number column of the even number row will be a ‘.’ denoting the node. Each of the odd number column of the even number row will either be a space denoting that there is no edge between the adjacent vertices or a ‘-‘ character denoting there is an edge. Each of the even number column of the odd number rows can be single ‘|’ denoting there is a vertical edge or a single space denoting there is no edge there. See the sample input for further clarification. Note in the sample input the spaces are replaced by S for readability. In the original input file they will be spaces.
For each test case output the number of ways you can add edges to the grid so that the grid is connected and form a tree. This result may be large. So output result%md. In the case the existing edges already creates a cycle output A line containing “Impossible” without the quotes.
|
6 2
2 1000 .S. SSS .S. 2
2 100 .-. |S| .S. 2
2 100 .-. |S| .-. 3
3 10000 .S.S. SSSSS .S.S. SSSSS .S.S. 3
3 10000 .-.-. SSSSS .-.-. SSSSS .-.-. 3
3 10000 .S.S. |S|S| .S.S. |S|S| .S.S. |
4 1 Impossible 192 9 9 |
Problem-setter: Abdullah al Mahmud
Special Thanks: Derek Kisman