首页 > 搜索 > DFS搜索 > HDU 3459-Rubik 2×2×2-DFS-[解题报告]HOJ
2014
03-30

HDU 3459-Rubik 2×2×2-DFS-[解题报告]HOJ

Rubik 2×2×2

问题描述 :

Sonny is probably the only computer science Ph.D. student who cannot solve a Rubik’s cube. One day, he came across a neat little 2×2×2 Rubik’s cube, and thought, "Finally, here’s a cube that’s easy enough for me to do!" Nope, wrong! He got pwned, hardcore. How embarrassing.To ensure that this does not happen again, he decides to write a computer program to solve the cube.
Then he had this brilliant idea: Why not have the students at the programming contest do the work instead? So, given an initial con guration of the 2×2×2 Rubik’s cube, your task for this problem is to write a program that solves it.
The mini-cube has 6 faces, each with 4 painted tiles on it. The faces are labeled Front (F), Back (B),Up (U), Down (D), Left (L), and Right (R), according to the diagram below. Each of the tiles on the faces can be colored Red (R), Green (G), Blue (B), Yellow (Y), Orange (O), or White (W), and there are exactly
4 instances of each color. The cube is considered solved when the colors of all tiles on each distinct face of the cube match.
You may use any combination of three distinct moves to transform the cube: a turn about the X-axis,a turn about the Y-axis, or a turn about the Z-axis. Each turn is exactly 90 degrees of all tiles on half the
cube, in the directions illustrated below. Note that the back-down-left corner is fixed with respect to all valid transforms.
Can you come up with a sequence of moves that will solve a given con guration of the Rubik’s cube?

输入:

You will be given maps of an "unwrapped" cubes showing colors on each of the faces, in the following format:
The letters in the above diagram shows you where to fi nd the colors on each face (as shown in the first diagram) from the map only { it is not valid input! The front face is oriented as in the diagram, with the other faces on the map attached to it so that it wraps to cover the cube. The letters on the faces may be any of R, G, B, Y, O, or W to indicate the color. Dot (.) characters serve to pad the map to a 6 × 8 grid,and are of no other signi cance.The input consists of several con guration maps in the format described, separated by blank lines. You may assume that each con guration is both valid and solvable. The end of input is denoted by an "empty" con guration consisting solely of `.’ characters; do not process this map.

输出:

You will be given maps of an "unwrapped" cubes showing colors on each of the faces, in the following format:
The letters in the above diagram shows you where to fi nd the colors on each face (as shown in the first diagram) from the map only { it is not valid input! The front face is oriented as in the diagram, with the other faces on the map attached to it so that it wraps to cover the cube. The letters on the faces may be any of R, G, B, Y, O, or W to indicate the color. Dot (.) characters serve to pad the map to a 6 × 8 grid,and are of no other signi cance.The input consists of several con guration maps in the format described, separated by blank lines. You may assume that each con guration is both valid and solvable. The end of input is denoted by an "empty" con guration consisting solely of `.’ characters; do not process this map.

样例输入:

..WO....
..WO....
BBOYGGWR
BBOYGGWR
..YR....
..YR....

..GY....
..BY....
ROYWRRBB
GWOWRBOW
..YG....
..OG....

........
........
........
........
........
........

样例输出:

X
YZXXXZYZXYXYZZYZZYZXYY

IDA*   

AC代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

char maps[10][10];
int maxdeep;
char ans[100];

int get_h(){
    int cnt = 0;
    if( maps[2][0] != maps[3][0] || maps[2][7] != maps[3][7] )  cnt++;
    if( maps[3][6] != maps[3][7] || maps[5][2] != maps[5][3] )  cnt++;
    if( maps[4][2] != maps[5][2] || maps[3][0] != maps[3][1] )  cnt++;
    return cnt;
}

bool check(){
    if( !( maps[0][2] == maps[0][3] && maps[0][3] == maps[1][2] && maps[1][2] == maps[1][3] ) ) return false;
    if( !( maps[2][2] == maps[2][3] && maps[2][3] == maps[3][2] && maps[3][2] == maps[3][3] ) ) return false;
    if( !( maps[4][2] == maps[4][3] && maps[4][3] == maps[5][2] && maps[5][2] == maps[5][3] ) ) return false;
    if( !( maps[2][0] == maps[2][1] && maps[2][1] == maps[3][0] && maps[3][0] == maps[3][1] ) ) return false;
    if( !( maps[2][4] == maps[2][5] && maps[2][5] == maps[3][4] && maps[3][4] == maps[3][5] ) ) return false;
    if( !( maps[2][6] == maps[2][7] && maps[2][7] == maps[3][6] && maps[3][6] == maps[3][7] ) ) return false;
    return true;
}

void rotation_x(){
    char temp1 = maps[5][3];
    char temp2 = maps[4][3];
    maps[5][3] = maps[3][3];
    maps[4][3] = maps[2][3];
    maps[3][3] = maps[1][3];
    maps[2][3] = maps[0][3];
    maps[1][3] = maps[2][6];
    maps[0][3] = maps[3][6];
    maps[2][6] = temp1;
    maps[3][6] = temp2;
    temp1 = maps[2][4];
    maps[2][4] = maps[2][5];
    maps[2][5] = maps[3][5];
    maps[3][5] = maps[3][4];
    maps[3][4] = temp1;
}

void rotation_y(){
    char temp1 = maps[2][7];
    char temp2 = maps[2][6];
    for( int i = 7; i >= 3; i -= 2 ){
        maps[2][i] = maps[2][i-2];
        maps[2][i-1] = maps[2][i-3];
    }
    maps[2][1] = temp1;
    maps[2][0] = temp2;
    char temp = maps[1][2];
    maps[1][2] = maps[0][2];
    maps[0][2] = maps[0][3];
    maps[0][3] = maps[1][3];
    maps[1][3] = temp;
}

void rotation_z(){
    char temp1 = maps[1][2];
    char temp2 = maps[1][3];
    maps[1][2] = maps[2][4];
    maps[1][3] = maps[3][4];
    maps[2][4] = maps[4][3];
    maps[3][4] = maps[4][2];
    maps[4][3] = maps[3][1];
    maps[4][2] = maps[2][1];
    maps[3][1] = temp1;
    maps[2][1] = temp2;
    char temp = maps[2][2];
    maps[2][2] = maps[2][3];
    maps[2][3] = maps[3][3];
    maps[3][3] = maps[3][2];
    maps[3][2] = temp;
}

void pf(){
    cout << endl;
    for( int i = 0; i < 6; i++ ){
        for( int j = 0; j < 8; j++ ){
            cout << maps[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

bool DFS( int deep ){
    if( deep + get_h() > maxdeep )  return false;
    if( deep == maxdeep )   return check();

    rotation_x();
  //  pf();
    ans[deep] = 'X';
    if( DFS( deep + 1 ) )   return true;
    rotation_x();rotation_x();rotation_x();

    rotation_y();
    ans[deep] = 'Y';
    if( DFS( deep + 1 ) )   return true;
    rotation_y();rotation_y();rotation_y();

    rotation_z();
    ans[deep] = 'Z';
    if( DFS( deep + 1 ) )   return true;
    rotation_z();rotation_z();rotation_z();

    return false;
}

int main(){
    while( 1 ){
        for( int i = 0; i < 6; i++ ){
            scanf( "%s", maps[i] );
        }
        if( maps[0][2] == '.' ){
            break;
        }
        maxdeep = 0;
        while( true ){
            maxdeep++;
            if( DFS( 0 ) ){
                break;
            }
        }
        for( int i = 0; i < maxdeep; i++ ){
            cout << ans[i];
        }
        cout << endl;
    }
    return 0;
}

参考:http://blog.csdn.net/hzh_0000/article/details/21990291


,
  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?