Hide

Problem I
Pipe Rotation

The four ninja turtles: Leonardo, Donatello, Michelangelo, and Raphael are seeking a new home in Manhattan, New York City. The turtles don’t like sudden dead-ends in their home. Fortunately, the government recently installed a new sewage system where pipes can be rotated! The turtles needs your help finding a suitable home, so they’re willing to provide you a grid of the current layout of the sewage system.

The grid consists of $N$ rows and $M$ columns. The cell $G_{i,j}$ will consist of one of four pipes, encoded as a letter between “A" and “D". These pipes can be rotated by any multiple of $90$ degrees:

\includegraphics[width=0.5\textwidth ]{pipe_rotation_1.png}

  • (A) Nothing

  • (B) Straight pipe (pipes leaving through two opposite edges)

  • (C) Elbow-shaped pipe (pipes leaving through two adjacent edges)

  • (D) Four-way pipe (pipes leaving through all four edges)

Determine whether it’s possible to rotate the cells such that the pipes all line up with one another. In particular, for each edge shared by a pair of adjacent cells, there must either be a pipe on both sides of that edge, or on neither side. And for each of the $2 \cdot (N + M)$ outer edges of the grid, there must be no pipe leaving through that edge. Below are examples:

\includegraphics[width=0.28\textwidth ]{pipe_rotation_2} Fig 1. Invalid example, two sudden dead-ends.
\includegraphics[width=0.28\textwidth ]{pipe_rotation_3} Fig 2. Valid example, no sudden dead-ends.

Input

The first line of input consists of two space-separated integers, $N$ and $M$ ($1 \leq N, M \leq 100$).
$N$ lines follow, the $i$th of which consists of $M$ characters $G_{i,1}, G_{i,2}, G_{i,j}, \dots , G_{i,M}$ and $G_{i,j} \in \{ A,B,C,D\} $ (for $i = 1..N$).

Output

Print, on a single line, a single string, either “Possible" if it’s possible to produce a valid configuration of pipes, or “Impossible" otherwise.

Sample Input 1 Sample Output 1
2 2
CC
CC
Possible
Sample Input 2 Sample Output 2
2 2
CC
CB
Impossible
Sample Input 3 Sample Output 3
3 3
CCC
CCC
CCC
Impossible
Sample Input 4 Sample Output 4
3 4
CBCA
BCDC
CCCC
Possible
Sample Input 5 Sample Output 5
5 2
CC
CC
AA
CC
CC
Possible

Please log in to submit a solution to this problem

Log in