ZOJ Problem Set - 2610
Little Georgie likes puzzles very much. Recently he has found a wooden triangle in the box with old toys. The side of the triangle is n inches long. The triangle is divided into n2 unit triangles with lines drawn on his surface.
The interesting fact about that triangle is that it is not solid - it consists of two parts. Each of the parts is a connected set of unit triangles. Georgie has put his triangle onto the table and now wonders whether he can separate the parts. He wants to separate them without taking any part of the triangle off the table, just moving the parts by the table surface. The triangle has a small but non-zero thickness, so while being moved the parts must not intersect.
For example, if the triangle is divided into parts as it is shown on the top picture below, Georgie can separate the parts the way he wants. However in the case displayed on the bottom picture, he cannot separate the parts without lifting one of them.
Help Georgie to determine whether he can separate the parts moving them by the surface of the table.
Input file contains one or more testcases. The first line of each testcase contains n (2 <= n <= 50). Next n lines contain the description of the triangle, i-th of these lines contains 2i - 1 characters, describing unit triangles in the i-th row, from left to right. Character '0' means that the triangle belongs to the first part of the main triangle, '1' means that it belongs to the second one.
Testcase with n = 0 designates the end of the test data, this testcase must not be processed. There is no blank line in the input file.
For each puzzle output the line with its number followed by the line that states whether the parts can be separated. Do not output any blank lines.
6 0 001 00011 0000011 000111111 00111111111 6 0 001 00111 0011011 000000111 00111111111 0
Puzzle 1 Parts can be separated Puzzle 2 Parts cannot be separated
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #7