1044 - Tiling the Plane

发布时间:2014-10-22 13:12:39编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1044 - Tiling the Plane",主要涉及到1044 - Tiling the Plane方面的内容,对于1044 - Tiling the Plane感兴趣的同学可以参考一下。

A polygon is said to ``tile the plane" if a collection of identical copies of the polygon can be assembled to fill an unbounded two-dimensional plane without any gaps or overlap. For example, Figure 1 shows an L-shaped polygon, and Figure 2 shows how a portion of the plane can be tiled with copies of the polygon. You must write a program to determine whether a given polygon can tile the plane. Each test case consists of a closed polygon in which every vertex is at a right angle and the length of every side is an integer multiple of a unit length. You may make as many copies of the polygon as you like, and you may move them over the plane, but you may not rotate or reflect any polygon. You might find the following information useful: It is known that there are only two fundamentally different tilings of the plane, the regular tiling by squares (chessboard tiling) and the tiling by regular hexagons (honeycomb tiling). A polygon can therefore tile the plane if and only if it satisfies one of the following two conditions: 1.There are points A, B, C, D in order on the polygon boundary (the points are not necessarily vertices of the polygon) such that the polygon boundaries from A to B and from D to C are congruent and the boundaries from B to C and from A to D are congruent. This leads to a tiling equivalent to the square tiling.2.There are points A, B, C, D, E, F in order on the polygon boundary, such that the boundary pairs AB and ED, BC and FE, CD and AF are congruent. This leads to a tiling equivalent to the hexagon tiling. Input  The input contains the descriptions of several polygons, each description consisting of one input line. Each description begins with an integer n (4n50) that represents the number of sides of the polygon. This number is followed by descriptions of n line segments which (taken in order) form a counterclockwise traversal of the perimeter of the polygon. Each line segment description consists of a letter followed by an integer. The letter is `N', `E', `S', or `W', representing the direction of the line segment as North, East, South, or West, respectively. The integer represents the length of the line segment as a multiple of the unit length. The described polygon will not touch or intersect itself. The input is terminated by a line consisting of the integer zero. Output  For each polygon in the input, print one output line. Print the number of the polygon in the input, followed by the word `Possible' if it is possible to tile the plane with the test polygon, or `Impossible' otherwise. Follow the format of the sample output. Sample Input  6 N 3 W 1 S 4 E 4 N 1 W 3 8 E 5 N 1 W 3 N 3 E 2 N 1 W 4 S 5 0 Sample Output  Polygon 1: Possible Polygon 2: Impossible #include<stdio.h> #include<string.h> #include<stdlib.h> char c[55],ch[5555],sequence_a[2777],sequence_b[2777]; int num[55],combo_a[2777],combo_b[2777],total[4],n,i,j,k,len,count,reverse,ok,cases; void tr(int i,int point) { int j,min,step; if(point>=len) { ok=1; return; } if(i>2) return; for(j=0;j<len-point;j++) { step=0; while(sequence_a[point+step]&&sequence_a[point+step]==sequence_b[j+step]) { if(combo_a[point+step]>combo_b[j+step]) min=combo_b[j+step]; else min=combo_a[point+step]; step+=min+1; } if(j+step>=len-point) tr(i+1,point+step); } } int main() { while(scanf("%d",&n)&&n) { memset(ch,0,sizeof(ch)); memset(sequence_a,0,sizeof(sequence_a)); memset(sequence_b,0,sizeof(sequence_b)); for(i=0;i<n;i++) scanf(" %c %d",&c[i],&num[i]); ok=0; for(i=0;i<n/2;i++) { len=0; for(j=0;j<n;j++) { count=(i+j)%n; for(k=0;k<num[count];k++) ch[len++]=c[count]; } count=0; for(j=0;j<4;j++) total[j]=0; for(j=len/2-1;j>=0;j--) { sequence_a[j]=ch[j]; if(ch[j]=='N') total[0]++; if(ch[j]=='S') total[1]++; if(ch[j]=='W') total[2]++; if(ch[j]=='E') total[3]++; if(j<len/2-1 && ch[j]==ch[j+1]) count++; else count=0; combo_a[j]=count; } count=0; for(j=len/2;j<len;j++) { reverse=len-j-1; if(ch[j]=='N') { sequence_b[reverse]='S'; total[1]--; } if(ch[j]=='S') { sequence_b[reverse]='N'; total[0]--; } if(ch[j]=='W') { sequence_b[reverse]='E'; total[3]--; } if(ch[j]=='E') { sequence_b[reverse]='W'; total[2]--; } if(j>len/2&&ch[j]==ch[j-1]) count++; else count=0; combo_b[reverse]=count; } for(j=0;j<4;j++) if(total[j]) break; if(j>3) { len/=2; tr(0,0); if(ok) break; } } printf("Polygon %d: ",++cases); if(ok) puts("Possible"); else puts("Impossible"); } return 0; }

上一篇:1043 - Crossing Streets