2013
12-11

# Rotations and Reflections

Many games, tricks and puzzles depend on determining whether two patterns on a rectangular grid are the “same” or not. For instance, the 96 different ways of arranging 8 queens safely on a chessboard can be shown to consist of rotations and/or reflections of only 12 basic patterns.

Write a program that will read in pairs of patterns and determine whether there is a simple transformation that will convert one into the other. Because symmetrical patterns bear many relationships to each other, the transformations must be checked in a specific order. The possible transformations (in order) are:

Preservation:           The patterns are identical

90 degree rotation :    The pattern was rotated clockwise by 90 degrees

180 degree rotation:    The pattern was rotated clockwise by 180 degrees

270 degree rotation:    The pattern was rotated clockwise by 270 degrees

Reflection:             The pattern was reflected about the horizontal axis (effectively by a mirror held at the top of the pattern)

Combination:            A reflection (as above), followed by one of the above rotations

Improper:               The patterns do not match under any of the above transformations

Input will consist of a series of pairs of patterns. Each set will consist of a line containing a single integer N (2 <= N <= 10) giving the size of the patterns, followed by N lines. Each line will consist of N dots or x’s (specifying a line of the original pattern), a space, and another set of N dots and x’s (specifying a line of the transformed pattern). The file will be terminated by a line consisting of a single zero (0).

Output will consist of a series of lines, one for each pattern pair in the input. Each line will consist of one of the following: Preserved’, Rotated through m degrees’ (where m is one of 90, 180 or 270), Reflected’, Reflected and rotated through m degrees’, Improper’.

5
x...x ....x
.x... ...x.
...x. .x...
..x.x ..x..
....x xx..x
2
x. xx
x. xx
4
..x. ...x
xx.. ....
.... xx..
...x ..x.
4
.x.. ..x.
.x.x x...
.... ..xx
..x. ....
0

Rotated through 90 degrees
Improper
Reflected
Reflected and rotated through 270 degrees

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 11
using namespace std;
struct Node
{
char map[10][N];
int flag;
};
char endstate[10][N];
Node t1,t2,t3;
int n,i,j,k;
bool isEnd(Node tt)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(tt.map[i][j]!=endstate[i][j])
return false;
}
}
return true;
}
void rt90()
{

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
t1.map[j][n-i-1]=t2.map[i][j];
}
}
}
void rt180()
{
rt90();
t3=t2;
t2=t1;
rt90();
t2=t3;
}
void rt270()
{
rt90();
t3=t2;
t2=t1;
rt90();
t2=t1;
rt90();
t2=t3;
}
void reflect()
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
t1.map[n-i-1][j]=t2.map[i][j];
}
}
}
void BFS()
{
queue<Node> qu;
if(isEnd(t1))
{
printf("Preserved\n");
return;
}
t1.flag=0;
qu.push(t1);
while(!qu.empty())
{
t2=qu.front();
qu.pop();
if(t2.flag==0)
{
t1.flag=1;
rt90();
if(isEnd(t1))
{
printf("Rotated through 90 degrees\n");
return;
}
rt180();

if(isEnd(t1))
{
printf("Rotated through 180 degrees\n");
return;
}
rt270();
if(isEnd(t1))
{
printf("Rotated through 270 degrees\n");
return;
}
reflect();
if(isEnd(t1))
{
printf("Reflected\n");
return;
}
qu.push(t1);
}
else if(t2.flag==1)
{
rt90();
if(isEnd(t1))
{
printf("Reflected and rotated through 90 degrees\n");
return;
}
rt180();
if(isEnd(t1))
{
printf("Reflected and rotated through 180 degrees\n");
return;
}
rt270();
if(isEnd(t1))
{
printf("Reflected and rotated through 270 degrees\n");
return;
}
printf("Improper\n");
}
}
}
int main()
{
while(scanf("%d",&n)&&n!=0)
{
for(i=0;i<n;i++)
{
scanf("%s%s",t1.map[i],endstate[i]);
}
BFS();
}
}`

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

3. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

4. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.