ZOJ-2477 매 직 큐 브[교체 심화+시 뮬 레이 션]

9200 단어 DFS
제목 링크:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2477
acm 를 접 한 후부 터 지금까지 ZOJ 의 문제 에 저촉 되 었 습 니 다.제 가 했 던 많은 ZOJ 의 문 제 는 대부분 주제 의 뜻 이 모호 하고 설명 이 잘 되 지 않 았 습 니 다.
이 문제 의 난점 은 검색 이 아니 라 문 제 를 보 는 질문 법 만 봐 도 교체 로 깊 어 지 는 것 임 을 알 아야 하지만 정 작 사람 을 무 너 뜨리 는 곳 은 어디 일 까?
먼저 큐 브 의 전개 도,어느 면 이 정면 이나 뒷면 인지 가리 키 지 않 으 면 대응 하 는 시계 반대 방향 도 달라 지 는데 제목 설명 이 없 으 면 어 떡 하 죠?어 쩌 겠 어 요?저 는 해 봐 야 겠 어 요.제 가 먼저 색인 을 1 로 하 는 이 면 을 입방 의 뒷면 으로 한 다음 에 시계 반대 방향 으로 회전 하 는 것 을 모 의 했 어 요.계속 WA 를 했 어 요.그리고 WA 의 원인 이 시계 반대 방향 인지 다른 곳 에서 잘 쓰 지 못 했 는 지 확신 할 수 없어 요.제 가 색인 을 1 로 하 는 이 면 을 정면 으로 할 때 시 뮬 레이 션 시계 반대 방향 코드 를 다시 수정 하면 AC 예요.정말 할 말 이 없다.
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INF = 0x3f3f3f3f;
const int Maxn = 4e5+10;

int cube[10][4][4];

bool check() {
    for(int i = 0; i < 6; ++i) {
        int tmp = cube[i][0][0];
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) if(tmp != cube[i][j][k]) {
                return false;
            }
        }
    }
    return true;
}

void Size(int x, int dir) {
    if(dir == 1) {
        swap(cube[x][0][0], cube[x][0][2]);
        swap(cube[x][0][0], cube[x][2][2]);
        swap(cube[x][0][0], cube[x][2][0]);
        swap(cube[x][0][1], cube[x][1][2]);
        swap(cube[x][0][1], cube[x][2][1]);
        swap(cube[x][0][1], cube[x][1][0]);
    } else {
        swap(cube[x][0][0], cube[x][2][0]);
        swap(cube[x][0][0], cube[x][2][2]);
        swap(cube[x][0][0], cube[x][0][2]);
        swap(cube[x][0][1], cube[x][1][0]);
        swap(cube[x][0][1], cube[x][2][1]);
        swap(cube[x][0][1], cube[x][1][2]);
    }
}

void solve(int x, int dir) {
    Size(x, dir);
    if(x == 1 && dir == 1) { //
        swap(cube[4][2][0], cube[2][0][0]); swap(cube[4][2][2], cube[2][2][0]);
        swap(cube[4][2][0], cube[5][0][2]); swap(cube[4][2][2], cube[5][0][0]);
        swap(cube[4][2][0], cube[0][2][2]); swap(cube[4][2][2], cube[0][0][2]);
        swap(cube[4][2][1], cube[2][1][0]);
        swap(cube[4][2][1], cube[5][0][1]);
        swap(cube[4][2][1], cube[0][1][2]);
    } else if(x == 1 && dir == -1) {
        swap(cube[4][2][0], cube[0][2][2]); swap(cube[4][2][2], cube[0][0][2]);
        swap(cube[4][2][0], cube[5][0][2]); swap(cube[4][2][2], cube[5][0][0]);
        swap(cube[4][2][0], cube[2][0][0]); swap(cube[4][2][2], cube[2][2][0]);
        swap(cube[4][2][1], cube[0][1][2]);
        swap(cube[4][2][1], cube[5][0][1]);
        swap(cube[4][2][1], cube[2][1][0]);
    }

    if(x == 3 && dir == -1) { //
        swap(cube[4][0][0], cube[2][0][2]); swap(cube[4][0][2], cube[2][2][2]);
        swap(cube[4][0][0], cube[5][2][2]); swap(cube[4][0][2], cube[5][2][0]);
        swap(cube[4][0][0], cube[0][2][0]); swap(cube[4][0][2], cube[0][0][0]);
        swap(cube[4][0][1], cube[2][1][2]);
        swap(cube[4][0][1], cube[5][2][1]);
        swap(cube[4][0][1], cube[0][1][0]);
    } else if(x == 3 && dir == 1) {
        swap(cube[4][0][0], cube[0][2][0]); swap(cube[4][0][2], cube[0][0][0]);
        swap(cube[4][0][0], cube[5][2][2]); swap(cube[4][0][2], cube[5][2][0]);
        swap(cube[4][0][0], cube[2][0][2]); swap(cube[4][0][2], cube[2][2][2]);
        swap(cube[4][0][1], cube[0][1][0]);
        swap(cube[4][0][1], cube[5][2][1]);
        swap(cube[4][0][1], cube[2][1][2]);
    }

    if(x == 2 && dir == -1) { //
        swap(cube[3][0][0], cube[4][2][2]); swap(cube[3][2][0], cube[4][0][2]);
        swap(cube[3][0][0], cube[1][2][2]); swap(cube[3][2][0], cube[1][0][2]);
        swap(cube[3][0][0], cube[5][2][2]); swap(cube[3][2][0], cube[5][0][2]);
        swap(cube[3][1][0], cube[4][1][2]);
        swap(cube[3][1][0], cube[1][1][2]);
        swap(cube[3][1][0], cube[5][1][2]);
    } else if(x == 2 && dir == 1) {
        swap(cube[3][0][0], cube[5][2][2]); swap(cube[3][2][0], cube[5][0][2]);
        swap(cube[3][0][0], cube[1][2][2]); swap(cube[3][2][0], cube[1][0][2]);
        swap(cube[3][0][0], cube[4][2][2]); swap(cube[3][2][0], cube[4][0][2]);
        swap(cube[3][1][0], cube[5][1][2]);
        swap(cube[3][1][0], cube[1][1][2]);
        swap(cube[3][1][0], cube[4][1][2]);
    }

    if(x == 0 && dir == 1) { //
        swap(cube[3][0][2], cube[4][2][0]); swap(cube[3][2][2], cube[4][0][0]);
        swap(cube[3][0][2], cube[1][2][0]); swap(cube[3][2][2], cube[1][0][0]);
        swap(cube[3][0][2], cube[5][2][0]); swap(cube[3][2][2], cube[5][0][0]);
        swap(cube[3][1][2], cube[4][1][0]);
        swap(cube[3][1][2], cube[1][1][0]);
        swap(cube[3][1][2], cube[5][1][0]);
    } else if(x == 0 && dir == -1) {
        swap(cube[3][0][2], cube[5][2][0]); swap(cube[3][2][2], cube[5][0][0]);
        swap(cube[3][0][2], cube[1][2][0]); swap(cube[3][2][2], cube[1][0][0]);
        swap(cube[3][0][2], cube[4][2][0]); swap(cube[3][2][2], cube[4][0][0]);
        swap(cube[3][1][2], cube[5][1][0]);
        swap(cube[3][1][2], cube[1][1][0]);
        swap(cube[3][1][2], cube[4][1][0]);
    }

    if(x == 5 && dir == -1) { //
        swap(cube[3][2][0], cube[2][2][0]); swap(cube[3][2][2], cube[2][2][2]);
        swap(cube[3][2][0], cube[1][2][0]); swap(cube[3][2][2], cube[1][2][2]);
        swap(cube[3][2][0], cube[0][2][0]); swap(cube[3][2][2], cube[0][2][2]);
        swap(cube[3][2][1], cube[2][2][1]);
        swap(cube[3][2][1], cube[1][2][1]);
        swap(cube[3][2][1], cube[0][2][1]);
    } else if(x == 5 && dir == 1) {
        swap(cube[3][2][0], cube[0][2][0]); swap(cube[3][2][2], cube[0][2][2]);
        swap(cube[3][2][0], cube[1][2][0]); swap(cube[3][2][2], cube[1][2][2]);
        swap(cube[3][2][0], cube[2][2][0]); swap(cube[3][2][2], cube[2][2][2]);
        swap(cube[3][2][1], cube[0][2][1]);
        swap(cube[3][2][1], cube[1][2][1]);
        swap(cube[3][2][1], cube[2][2][1]);
    }

    if(x == 4 && dir == -1) { //
        swap(cube[0][0][0], cube[1][0][0]); swap(cube[0][0][2], cube[1][0][2]);
        swap(cube[0][0][0], cube[2][0][0]); swap(cube[0][0][2], cube[2][0][2]);
        swap(cube[0][0][0], cube[3][0][0]); swap(cube[0][0][2], cube[3][0][2]);
        swap(cube[0][0][1], cube[1][0][1]);
        swap(cube[0][0][1], cube[2][0][1]);
        swap(cube[0][0][1], cube[3][0][1]);
    } else if(x == 4 && dir == 1) {
        swap(cube[0][0][0], cube[3][0][0]); swap(cube[0][0][2], cube[3][0][2]);
        swap(cube[0][0][0], cube[2][0][0]); swap(cube[0][0][2], cube[2][0][2]);
        swap(cube[0][0][0], cube[1][0][0]); swap(cube[0][0][2], cube[1][0][2]);
        swap(cube[0][0][1], cube[3][0][1]);
        swap(cube[0][0][1], cube[2][0][1]);
        swap(cube[0][0][1], cube[1][0][1]);
    }
}

int ans[10][2], cnt;

void print() {
    for(int i = 0; i < 6; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) cout << cube[i][j][k] << " ";
            cout << endl;
        }
        cout << endl;
    }
}

bool dfs(int dep, int step) {
    if(check()) return true;
    if(step == dep) return false;

    for(int i = 0; i < 6; ++i) {
        ans[cnt][0] = i; ans[cnt][1] = -1;
        cnt++; solve(i, -1);
        if(dfs(dep, step+1)) return true;
        cnt--; solve(i, 1);

        ans[cnt][0] = i; ans[cnt][1] = 1;
        cnt++; solve(i, 1);
        if(dfs(dep, step+1)) return true;
        cnt--; solve(i, -1);
    }
    return false;
}

int main(void)
{
    int T;
    scanf("%d", &T);
    while(T--) {
        int r = 0, c = 0;
        while(r < 2 || c < 3) {
            char ch = getchar();
            if(c == 3) {
                c = 0; r++;
            }
            if(ch >= 'a' && ch <= 'z') cube[4][r][c++] = ch-'a';
        }
        r = 0; c = 0;
        while(r < 2 || c < 12) {
            char ch = getchar();
            if(c == 12) {
                c = 0; r++;
            }
            if(ch < 'a' || ch > 'z') continue;
            if(c < 3) cube[0][r][c] = ch-'a';
            else if(c < 6) cube[1][r][c-3] = ch-'a';
            else if(c < 9) cube[2][r][c-6] = ch-'a';
            else cube[3][r][c-9] = ch-'a';
            c++;
        }
        r = 0; c = 0;
        while(r < 2 || c < 3) {
            char ch = getchar();
            if(c == 3) {
                c = 0; r++;
            }
            if(ch >= 'a' && ch <= 'z') cube[5][r][c++] = ch-'a';
        }
      //  print();
        cnt = 0; bool ok = false;

        for(int dep = 1; dep <= 5; ++dep) {
            if(dfs(dep, 0)) {
                ok = true; break;
            }
        }
        if(!ok) printf("-1
"); else { printf("%d
", cnt); for(int i = 0; i < cnt; ++i) printf("%d %d
", ans[i][0], ans[i][1]); } } return 0; }

좋은 웹페이지 즐겨찾기