首页 > ACM题库 > HDU-杭电 > hdu 1993 Spatial Concepts Test-计算几何[解题报告]C++
2013
12-26

hdu 1993 Spatial Concepts Test-计算几何[解题报告]C++

Spatial Concepts Test

问题描述 :

The Flathead Testing Corporation (FTC) supplies various tests for Human Resources departments at many companies. One type of test they supply includes spatial concepts questions such as:
When the following figure is folded back on the interior lines it forms a cube.
Which of the following could be an image of one corner of the resulting cube?
Unfortunately, FTC was recently embarrassed when one such question on a test had no solution among the choices and another (given in the example) had two solutions among the choices (1 and 3).
FTC needs a routine which will read in a specification of the unfolded cube and specifications of corner views and determine, for each corner view, whether it is a view of a corner of the cube specified in the unfolded part.
FTC uses the following images as faces of each cube. Each image is symmetrical about the vertical axis and has a distinguished end (up in each image).

The unfolded cube is specified by a string of six pairs of a letter indicating the image on the face and a number indicating the orientation of the distinguished end of the face: 1 is up, 2 is right, 3 is down and 4 is left. The faces are specified in the order given in the following figure with the orientations indicated in the square to the right:

So the unfolded cube in the example is specified as “F3E4E2D3C2F3”. FTC has a routine which reads this specification and generates the unfolded image for the question.
The answer images are specified by three pairs of a letter and a digit indicating a face image and an orientation as indicated in the following diagram. The faces are specified in the order top, right, left (indicated by numbers in brackets in the figures), that is clockwise around the center vertex starting at the top. The orientation of the distinguished end of each face is indicated by the numbers on the edges in the diagram. They circle each face clockwise, starting at the center vertex.

For the example, the answer figures are specified as “C2D2F2”, “E3F3C4”, “F2C2D2”, “D1E1F3” and “E1C1E1”. Again, FTC has a routine which reads this specification and generates each answer image for the question. They just need your routine to make sure there is exactly one correct answer to each question.

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of six lines of input. The first line of input is the specification for the folded out cube as described above. This line is followed by five lines, each of which gives the specification of one answer image as described above.

输出:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of six lines of input. The first line of input is the specification for the folded out cube as described above. This line is followed by five lines, each of which gives the specification of one answer image as described above.

样例输入:

2
F3E4E2D3C2F3
C2D2F2
E3F3C4
F2C2D2
D1E1F3
E1C1E1
A2F4F1A3A3C4
C3A4A2
F3F4A1
F3C4A1
A2C3A2
A4A4F1

样例输出:

1 2 Y N Y N N
2 0 N N N N N

很烦的一道题我是枚举出以每一个面为中心时,他的四个方向的情况
然后再将答案中给出的一种可能,旋转在同可能的状态比较

#include <iostream>
 #include <vector>
 using namespace std;

 class face
 {
 public:
     char C;
     int dir;
     void rotate(int k)
     {
         dir = (dir + k) % 4;
     }
 };

 class state
 {
 public:
     face link[4];
     face mid;
 public:
     void rotate()
     {
         mid.rotate(1);
         face temp = link[3];

         for (int i = 3; i > 0; i--)
             link[i] = link[i-1];
         link[0] = temp;

         for (int i = 0; i < 4; i++)
             link[i].rotate(1);
     }
     bool Compare(state a)
     {
         if (mid.C != a.mid.C || mid.dir != a.mid.dir) return false;

         for (int i = 0; i < 4; i++)
         {
             if (a.link[i].C == '*' || (a.link[i].C == link[i].C && a.link[i].dir == link[i].dir)) continue;
             return false;
         }
         return true;
     }
 };

 face cube[6];

 state P[6];

 bool Find(state ans)
 {
     for (int i = 0; i < 6; i++)
     {
         for (int j = 0; j < 4; j++)
         {
             ans.rotate();
             if (P[i].Compare(ans)) return true;
         }
     }

     return false;
 }

 int main()
 {
     int T;
     scanf("%d", &T);
     getchar();
     for (int ctr = 1; ctr <= T; ctr++)
     {
         vector<int> ret;
             ret.clear();
             int tot = 0;
         for (int i = 0; i < 6; i++)
         {
             char ch;
             int d;
             scanf("%c%d", &ch, &d);
             d--;
             cube[i].C = ch;
             cube[i].dir = d;
         }
         getchar();

         P[0].mid = cube[0];
         P[0].link[0] = cube[4],P[0].link[0].rotate(2);
         P[0].link[1] = cube[3],P[0].link[1].rotate(3);
         P[0].link[2] = cube[2];
         P[0].link[3] = cube[1],P[0].link[3].rotate(1);

         P[1].mid = cube[1];
         P[1].link[0] = cube[0],P[1].link[0].rotate(3);
         P[1].link[1] = cube[2];
         P[1].link[2] = cube[5],P[1].link[2].rotate(1);
         P[1].link[3] = cube[4];

         P[2].mid = cube[2];
         P[2].link[0] = cube[0];
         P[2].link[1] = cube[3];
         P[2].link[2] = cube[5];
         P[2].link[3] = cube[1];

         P[3].mid = cube[3];
         P[3].link[0] = cube[0],P[3].link[0].rotate(1);
         P[3].link[1] = cube[4];
         P[3].link[2] = cube[5],P[3].link[2].rotate(3);
         P[3].link[3] = cube[2];

         P[4].mid = cube[4];
         P[4].link[0] = cube[0],P[4].link[0].rotate(2);
         P[4].link[1] = cube[1];
         P[4].link[2] = cube[5],P[4].link[2].rotate(2);
         P[4].link[3] = cube[3];

         P[5].mid = cube[5];
         P[5].link[0] = cube[2];
         P[5].link[1] = cube[3],P[5].link[1].rotate(1);
         P[5].link[2] = cube[4],P[5].link[2].rotate(2);
         P[5].link[3] = cube[1],P[5].link[3].rotate(3);

         for (int i = 0; i < 5; i++)
         {

             state ans;
             for (int j = 0; j < 3; j++)
             {
                 char ch;
                 int d;
                 scanf("%c%d", &ch, &d);
                 d--;
                 if (j == 0) 
                 {
                     ans.mid.C = ch;
                     ans.mid.dir = d;
                 }
                 else
                 {
                     ans.link[j].C = ch;
                     ans.link[j].dir = d;
                 }
             }
             getchar();
             ans.mid.rotate (2);
             ans.link[1].rotate(3);
             ans.link[2].rotate(1);
             ans.link[0].C = '*';
             ans.link[3].C = '*';
             if (Find(ans)) tot+=1, ret.push_back(1);
             else
                 ret.push_back(0);

         }
         printf("%d ", ctr);
         printf("%d", tot);
             for (int i = 0; i < 5; i++)
                 if (ret[i])
                     printf(" Y");
                 else
                     printf(" N");
             printf("\n");
     }

     return 0;
 }

 


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.