ZOJ Problem Set - 2566
In the middle of the XX-th century Roger Penrose impressed many mathematicians showing that there exists a set of tiles that can cover the whole plane, but only aperiodically. On the contrary, in this problem we are interested in periodic tilings, more of that, in regular tilings. Consider a connected set of unit squares. It is called a polyomino. A polyomino is said to tile the plane in a regular way, if one can cover the whole plane with non-overlapping copies of the selected polyomino in such a way that:
Given a polyomino, find out if it is possible to tile the plane with it in a regular way. You may find useful the following fact: if it is possible to tile the plane with some polyomino in a regular way, then in the tiling each polyomino has a common border of non-zero length with at most six other polyominoes.
There are severval test cases.The first line of each test case is a positive integen n(0<n<=50).Then there're n lines of characters. The n lines describes a part of the plane that contains the given polyomino, represented by the characters '.'(dot) denoting empty spaces and '*'(asterisk) denoting squares that belong to the polyomino. each line contains at most 50 characters. The polyomino is constructed of at most 30 unit squares. The input is terminaled by EOF.
There is only one line for each test case. Output "YES" if it is possible to tile the plane in a regular way with the polyomino given, or "NO" if it is impossible.
4 .... .*.. .**. ..... 4 .... .*.. .**.* ..*** 5 .... .***. ..*.. .***. ..*..
YES NO YES
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4