
ZOJ Problem Set  2566
In the middle of the XXth 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 nonoverlapping 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 nonzero length with at most six other polyominoes. Input 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. Output 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. Sample Input 4 .... .*.. .**. ..... 4 .... .*.. .**.* ..*** 5 .... .***. ..*.. .***. ..*.. Sample Output YES NO YES Author: Andrew Stankevich Source: Andrew Stankevich's Contest #4 