一道ACM的习题，求高手解答

Question

RT.题目如下：
魔板由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。
其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作：
A操作（上下行互换）：
8 7 6 5
1 2 3 4
B操作（每次以行循环右移一个）：
4 1 2 3
5 8 7 6
C操作（中间四小块顺时针转一格）：
1 7 2 4
8 6 3 5
用上述三种基本操作，可将任一种状态装换成另一种状态。
[输入]标准输入stdin
输入包括多个要求解的魔板，每个魔板用三行描述。
第一行步数N（不超过10的整数），表示最多容许的步数。
第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。
当N等于-1的时候，表示输入结束。
4
5 8 7 6
4 1 2 3
3
8 7 6 5
1 2 3 4
-1
[输出] 标准输出 stdout
对于每一个要求解的魔板，输出一行。
首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格。
注意：如果不能达到，则M输出-1即可。
2 AB
1 A注：最好用java实现，C或C++也可。

Answer 1

这个题里限定了 不会超过 10 步
可以把问题转化成 A B C 组成的长度为 10 的字串有多少（59049）
其中需要满足以下条件
2 个 A 之间必有 C（2 个 A间如果没有 C 就没意思了，这个可以从其他的字串的子串中得到）
4 个 B 之间必有 C （道理同上）
4 个 C 之间必有 A 或 B （道理同上）
这样剩下的字串就不是太多了
再在这些字串中以首字符开始遍历每一个子串
把结果和目标对比下
直到找到符合要求的为止感觉这样比较慢
等待高手提供好的算法

Answer 2

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;public class Main
{
    static int from_ar(int[] ar)
    {
        int v=0;
        for(int i=7;i>=0;i--)
            v = v*10 + ar[i];
        return v;
    }
    static void to_ar(int val,int[] ar)
    {
        for(int i=0;i<8;i++)
        {
            ar[i] = val%10;
            val/=10;
        }
    }
    
    static int A(int[] from,int[] to)
    {
        for(int i=0;i<8;i++)
            to[(i+4)%8] = from[i];
        return from_ar(to);
    }
    static int B(int[] from,int[] to)
    {
        for(int i=0;i<4;i++)
        {
            to[(i+3)%4] = from[i];
            to[(i+3)%4+4] = from[i+4];
        }
        return from_ar(to);
    }
    static int C(int[] from,int [] to)
    {
        to[0] = from[0];
        to[1] = from[5];
        to[2] = from[1];
        to[3] = from[3];
        to[4] = from[4];
        to[5] = from[6];
        to[6] = from[2];
        to[7] = from[7];
        return from_ar(to);
    }
    static class Step
    {
        char op;
        Step prev;
        int value;
        Step(int value,char op,Step prev)
        {
            this.value = value;
            this.op = op;
            this.prev = prev;
        }
        void output0()
        {
            if(prev != null)
            {
                prev.output0();
                System.out.print(op);
            }
        }
        int step_count()
        {
            if(prev == null)
                return 0;
            return prev.step_count()+1;
        }
        void ouput()
        {
            if(prev == null)
                System.out.println(0);
            else
            {
                System.out.print(step_count() + " ");
                output0();
                System.out.println();
            }
        }
    }
    static int doOp(int op,int[] from,int[] to)
    {
        switch(op)
        {
        case 0: return A(from,to); 
        case 1: return B(from,to);
        default:return C(from,to);
        }
    }
    static final int init_value = 12348765;
    static final Step init_step = new Step(init_value,' ',null);
    static Step calc(int steps,int target)
    {
        if(target == init_value)
            return init_step;
        int[] from = new int[8];
        int[] to = new int[8];
        to_ar(init_value,from);
        HashMap<Integer,Step> map = new HashMap<Integer,Step>();
        ArrayList<Step> nexts = new ArrayList<Step>();
        
        map.put(init_value,init_step);
        nexts.add(init_step);
        for(int i=0;i<steps;i++)
        {
            ArrayList<Step> curs = nexts;
            nexts = new ArrayList<Step>();
            for(Step cur:curs)
            {
                to_ar(cur.value,from);
                for(int j=0;j<3;j++)
                {
                    int val1 = doOp(j,from,to);
                    if(!map.containsKey(val1))
                    {
                        Step step = new Step(val1,(char)('A'+j),cur);
                        if(val1 == target)
                            return step;
                        map.put(val1,step);
                        nexts.add(step);
                    }
                }
            }
        }
        return null;
    }
    public static void main(String[] args) throws Exception
    {
        Scanner in = new Scanner(System.in);
        for(;;)
        {
            int steps = in.nextInt();
            if(steps<0)
                break;
            int val = 0;
            for(int i=0;i<8;i++)
                val = val*10 + in.nextInt();
            Step r = calc(steps,val);
            if(r == null)
                System.out.println(-1);
            else
                r.ouput();
        }
    }
}