【题解】UVa 1343【The Rotation Game】

分析

这题是一道经典的A*。

代码

#include<cstdio>
#include<algorithm>
using std::min;
int line[8][7] = {
    { 0, 2, 6,11,15,20,22},//A
    { 1, 3, 8,12,17,21,23},//B
    {10, 9, 8, 7, 6, 5, 4},//C
    {19,18,17,16,15,14,13},//D
};
const int rev[8] = { 5, 4, 7, 6, 1, 0, 3, 2};
const int center[8] = { 6, 7, 8, 11,12,15,16,17};
int A[24];
char ans[1000];

bool isFinal(){
    for(int i = 0;i < 8;i++) if(A[center[i]] != A[center[0]]) return false;
    return true;
}

int diff(int target){
    int ans = 0;
    for(int i = 0;i < 8;i++) if(A[center[i]] != target) ans++;
    return ans;
}
inline int oysj(){return min(min(diff(1),diff(2)),diff(3));}
inline void move(int i){
    int delta = A[line[i][0]];
    for(int j = 0;j < 6;j++) A[line[i][j]] = A[line[i][j + 1]];
    A[line[i][6]] = delta;
}

bool dfs(int d,int maxd){
    if(isFinal()){ans[d] = '\0';printf("%s\n",ans);return true;}
    if(d + oysj() > maxd) return false;
    for(int i = 0;i < 8;i++){
        ans[d] = 'A' + i;
        move(i);
        if(dfs(d + 1,maxd)) return true;
        move(rev[i]);
    }
    return false;
}

int main(){
    for(int i = 4;i < 8;i++) for(int j = 0;j < 7;j++) line[i][j] = line[rev[i]][6 - j];
    while(scanf("%d",&A[0]) == 1 && A[0]){
        for(int i = 1;i < 24;i++) scanf("%d",&A[i]);
        for(int i = 0;i < 24;i++) if(!A[i]) return 0;
        if(isFinal()) printf("No moves needed\n");
        else for(int maxd = 1;;maxd++) if(dfs(0,maxd)) break;
        printf("%d\n",A[6]);
    }

    return 0;
}