Problem G
Cairo Corridor
The Cairo pentagonal tiling is a decomposition of the plane using semiregular pentagons. Its name is given because several streets in Cairo are paved using variations of this design.
Consider a bounded tiling where each pentagon is either clear (white) or filled in (grey). A corridor is a maximal set of clear adjacent pentagons that connect the four borders of the tiling. Pentagons are considered adjacent if they share an edge, not just a corner. It is easy to verify that there can be at most one corridor in each tiling. A corridor is said to be minimal if it has no superfluous pentagon, that is, if any pentagon of the corridor was filled in, the set of remaining pentagons would not be a corridor.
|
(a) Minimal corridor |
(b) Minimal corridor |
(c) No minimal corridor |
(d) No corridor |
|
|
|
|
|
![\includegraphics[width=0.95\textwidth ]{corridor3.png}](/problems/cairocorridor/file/statement/en/img-0002.png)
![\includegraphics[width=0.95\textwidth ]{corridor2.png}](/problems/cairocorridor/file/statement/en/img-0003.png)
![\includegraphics[width=0.95\textwidth ]{corridor5.png}](/problems/cairocorridor/file/statement/en/img-0004.png)
![\includegraphics[width=0.95\textwidth ]{corridor6.png}](/problems/cairocorridor/file/statement/en/img-0005.png)
The figure above depicts four example tilings. In the first three cases, there is a corridor which is highlighted in yellow. Besides, the corridors of figures (a) and (b) are minimal, but the one in figure (c) is not: for example, the tiles marked ‘X’ (among others) could be filled in and a corridor would still exist. In the rightmost tiling there is no corridor.
The tilings shown in figures (a) and (c) correspond to sample input 1.
Task
Write a program that reads textual descriptions of Cairo tilings, and for each one determines if a corridor exists and is minimal. In the latter case, the program should compute the size of the corridor, i.e., the number of clear pentagonal tiles of the corridor.
Input
The first line of input is a positive decimal integer $T$ of tilings to be processed. Each tiling description $k$ has a first line with two positive decimal integers, $N_ k$ and $M_ k$, separated by a space. The following $N_ k$ lines contain $2 \cdot M_ k$ binary digits representing pairs $a_{ij}, b_{ij}$ of tiles (0 is clear and 1 is full) in alternating horizontal/vertical adjacency following a “checkerboard” pattern, as is illustrated in the figure below.
![\includegraphics[width=0.45\textwidth ]{inputformat2.png}](/problems/cairocorridor/file/statement/en/img-0006.png)
Constraints
|
$1$ |
$\leq $ |
$T$ |
$\leq $ |
$10$ |
Number of tilings |
|
$1$ |
$\leq $ |
$\sum _{k=1}^ T N_ k$ |
$\leq $ |
$250$ |
Total number of lines |
|
$1$ |
$\leq $ |
$\sum _{k=1}^ T M_ k$ |
$\leq $ |
$250$ |
Total number of tile pairs |
Output
The output consists of $T$ lines; the $k$-th line should be the size of the corridor of the $k$-th tiling, if there exists a minimal corridor, and NO MINIMAL CORRIDOR, otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 6 6 010101001001 001000101100 110101001101 010010000100 001110110010 001001101010 6 6 010010110010 001100100111 000110100101 011001100101 100100011100 011010001101 |
17 NO MINIMAL CORRIDOR |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 3 4 11110111 01000000 11110111 |
9 |
