首页 > 搜索 > BFS搜索 > HDU 1461 Rotations and Reflections-BFS-[解题报告] C++
2013
12-11

HDU 1461 Rotations and Reflections-BFS-[解题报告] C++

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

认真把题目读完,你就会发现  最终状态只会是题目描述的那几种。 bfs水过

#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();
    }
}

解题报告转自:http://blog.csdn.net/qq403977698/article/details/8059184


,
  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.