程序设计大赛第二题

Question

用C++或Java或C语言均可以，谢谢青年节
Description 
5.4青年节就要到了。作为大学生自己的节日，学校将要举行各种各样的活动，舞蹈将是一个重要的比赛项目，数学计算机学院需要排练一个舞蹈节目参赛。ACMer们也想为活动做点贡献。一天，AllStar09-1和AllStar09-2来到排练场地（神曰：是做贡献还是看mm，是个问题！），对于舞蹈语言他们一窍不通，但是他们发现八位mm在表演舞蹈时不断变换“队形矩阵”（专业俗语！）。 
假设队形以及变换的规则如下： 
A变换：将上下两行互换 
B变换：将上下两行同时循环右移一位 
C变换：将中间的四人顺时针旋转一个位置 变换前队形 
1234 
8765 
A变换后队形 
8765 
1234 
B变换后队形 
4123 
5876 
C变换后队形 
1724 
8635 现在的问题是，在某一种状态下，如果8次变换后还不能变回初始队形，则就无法在音乐结束前完成舞蹈。 
AllStar09-1和AllStar09-2决定帮助mm们解决这个问题。计算出在某一种队形矩阵状态下，经过最少多少次变换才能变换为初始队形？ 
初始队形为： 
1234 
8765 Input 输入包括多行，每行包括一个数字串，前四个为第一行，后四个为第二行。数字串输入合法。 
以00000000结束（00000000不需要判断） Output 
对于每组测试数据，输出一行，为最少步数。如果8次变换后还不能回到初始队形，输出-1。 Sample Input 12348765
23417658
12345678
17248635
00000000Sample Output 0
1
-1
3

Answer 1

A变换：将上下两行互换 
B变换：将上下两行同时循环右移一位 
C变换：将中间的四人顺时针旋转一个位置 变换前队形 
1234 
8765 
A变换后队形 
8765 
1234 
B变换后队形 
4123 
5876 
C变换后队形 
1724 
8635 
-------------------
B变化和C变换的描述与示例有些问题B变换似乎是循环右移1位后，上下两排再交换。而C变换则完全看不出规律。

Answer 2

public class T {
static int time = 0; /**
 * 说一下我的思路，先进行B变换，因为这个变换可使得整个数组发生彻底的变化，然后进行C变换，最后A变换
 * 
 * @param args
 */
public static void main(String[] args) {
String s = "24173586";
diGui(string2Byte(s));
// s = "72416358"
// 测试结果B exchange
// C exchange
// C exchange
// C exchange
// 4
} private static void diGui(byte[][] a) {
if (time <= 8) {
if (right_B(a)) {
if (right_C(a)) {
if (right_A(a)) {
if (is_Right_Result(a)) {
System.out.println(time + "才变换");
} else {
A_Exchange(a);
time++;
System.out.println(time + "次变换");
}
} else {
C_Exchange(a);
time++;
diGui(a);
}
} else {
C_Exchange(a);
time++;
diGui(a);
} } else {
B_Exchange(a);
time++;
diGui(a);
}
}
else{
System.out.println("8次内不能变换成功");
} } private static boolean can_C_Exchange(byte[][] a) {// 除了正确顺序之外的顺序
// 要求必须是那几个数字，但不包括经A变换后的
if (a.length != 4 || a[0].length != 4)
return false;
else {
if ((a[0][1] == 6 && a[0][2] == 7 && a[1][1] == 3 && a[1][2] == 2)
|| (a[0][1] == 7 && a[0][2] == 2 && a[1][1] == 6 && a[1][2] == 3)
|| (a[0][1] == 3 && a[0][2] == 6 && a[1][1] == 2 && a[1][2] == 7))
return true;
else
return false;
}
} private static byte[][] C_Exchange(byte[][] a) {
if (can_C_Exchange(a)) {
byte temp = a[0][2];
a[0][2] = a[0][1];
a[0][1] = a[1][1];
a[1][1] = a[1][2];
a[1][2] = temp;
System.out.println("C exchange");
return a;
}
return a;
} private static byte[][] B_Exchange(byte[][] a) { // 是右循环一位对换，不是前后对调
byte temp1 = a[0][0];
a[0][0] = a[0][3];
a[0][3] = a[0][2];
a[0][2] = a[0][1];
a[0][1] = temp1; byte temp2 = a[1][0];
a[1][0] = a[1][3];
a[1][3] = a[1][2];
a[1][2] = a[1][1];
a[1][1] = temp2;
System.out.println("B exchange"); return a;
} private static boolean can_A_Exchange(byte[][] a) { // 8765 1234的时候
if (a.length != 4 || a[0].length != 4)
return false;
else {
for (int i = 0; i < a[0].length; i++) {
if (a[0][i] != 9 - i - 1 || a[1][i] != i + 1)
return false;
}
return true;
} } private static byte[][] A_Exchange(byte[][] a) {
if (can_A_Exchange(a)) {
for (int i = 0; i < a[0].length; i++) {
byte temp = a[0][i];
a[0][i] = a[1][i];
a[1][i] = temp;
}
System.out.println("A exchange");
return a;
}
return a;
} private static byte[][] string2Byte(String s) {
if (s.length() != 8)
return new byte[][] {};
else {
char[] c = s.toCharArray();
byte[] temp = new byte[c.length];
for (int i = 0; i < c.length; i++) {
temp[i] = (byte) Integer.parseInt(c[i] + "");
}
byte[][] rtn = new byte[4][4];
System.arraycopy(temp, 0, rtn[0], 0, 4);
System.arraycopy(temp, 4, rtn[1], 0, 4);
return rtn;
}
} private static boolean is_Right_Result(byte[][] a) {
for (int i = 0; i < a[0].length; i++) {
if (a[0][i] != i + 1 || a[1][i] != 9 - i - 1) {
return false;
}
}
return true;
} private static boolean right_C(byte[][] a) { // C交换时 位置上必须是这些数字
if ((a[0][1] == 2 && a[0][2] == 3 && a[1][1] == 7 && a[1][2] == 6)
|| (a[0][1] == 7 && a[0][2] == 6 && a[1][1] == 2 && a[1][2] == 3))// 可以通过一步A交换得到正确顺序
// 也算正确C
return true;
else
return false;
} private static boolean right_B(byte[][] a) { // 是不是1..4 8..5 或者是它经过A变换
if ((a[0][0] == 1 && a[1][0] == 8 && a[0][3] == 4 && a[1][3] == 5)
|| (a[0][0] == 8 && a[1][0] == 1 && a[0][3] == 5 && a[1][3] == 4))// 可以通过一步A交换得到正确顺序
// 也算正确B
return true;
else
return false;
} private static boolean right_A(byte[][] a) { // 包括最后的正确顺序 但也包括经过一步A变换
for (int i = 0; i < a[0].length; i++) {
if ((a[1][i] != i + 1 || a[0][i] != 9 - i - 1) && // 8765 1234
(a[0][i] != i + 1 || a[1][i] != 9 - i - 1)) { // 1234 8765
return false;
}
}
return true;
}
}

Answer 3

汗稍微改一下
else {
A_Exchange(a);
time++;
diGui(a);//把打印改成这个
}

Answer 4

从原始队形出发，进行逆变换。计算出所有可能的队形，及其所需的最小步数，将结果缓存到HashMap。处理测试数据时直接到缓存里查。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;public class Main {    private static final String orig = "12348765";
    private static final Map<String, String> tCache = new HashMap<String, String>();
    private static final Map<String, Integer> vCache = new HashMap<String, Integer>();
    private static final Queue<String> patternQ = new LinkedList<String>();    public static void main(String[] args) throws Exception {
        initialize();
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in));
        String v = reader.readLine();        
        while (!v.equals("00000000")) {
            Integer out = vCache.get(v);
            if (out == null) {
                out = -1;
            }
            System.out.println(out);
            v = reader.readLine();
        }
    }    // 遍历所有逆变换序列
    private static void initialize() {
        patternQ.offer("");
        String pattern = patternQ.poll();
        while (pattern != null) {
            if (pattern.length() < 8) {
                patternQ.offer(pattern + "a");
                patternQ.offer(pattern + "b");
                patternQ.offer(pattern + "c");
            }
            String key = t(pattern);
            if (vCache.get(t(pattern)) == null) {            
                vCache.put(key, pattern.length());
            }
            pattern = patternQ.poll();
        }
    }    // 计算逆变换序列后的队形
    private static String t(String pattern) {
        String result = tCache.get(pattern);    
        if (result != null) {
            return result;
        }
        if (pattern.isEmpty()) {
            result = orig;
        } else {
            switch (pattern.charAt(pattern.length() - 1)) {
            case 'a':
                result = a(t(pattern.substring(0, pattern.length() - 1)));
                break;
            case 'b':
                result = b(t(pattern.substring(0, pattern.length() - 1)));
                break;
            case 'c':
                result = c(t(pattern.substring(0, pattern.length() - 1)));
                break;
            }            
        }
        tCache.put(pattern, result.intern());
        return result;
    }
    
    // A的逆变换
    private static String a(String v) {
        return v.substring(4, 8) + v.substring(0, 4);
    }    // B的逆变换
    private static String b(String v) {
        return v.substring(1, 4) + v.charAt(0)
             + v.substring(5, 8) + v.charAt(4);
    }    // C的逆变换
    private static String c(String v) {
        return v.substring(0, 1) + v.charAt(2) + v.charAt(6) + v.charAt(3)
                   + v.charAt(4) + v.charAt(1) + v.charAt(5) + v.charAt(7);
    }
}

Answer 5

哦，恍然大悟，我理解错了，我以为B变化是基于A变换结果，而C变换的示例是基于B变换结果。
原来都是基于原始队列的示例。

Answer 6

趁中午休息偷个空做一下
注释偷懒不写了，因为觉得也没什么不好理解的
只是以例子数据作了测试import java.util.*;public class DanceMatrixMain {    /**
     * <p>
     * </p>
     *
     * @param args
     */
    public static void main(String[] args) {
        try {
            /* sample input
               12348765 
               23417658 
               12345678 
               17248635 
               00000000 
               
               sample output
               0 
               1 
               -1 
               3 
             */
            String[] input = MatrixFactory.nextMatrix();
            //String[] input = {"12348765", "23417658", "12345678", "17248635"};
            System.out.println("----------output is----------");
            for (String s : input) {
                System.out.println(new MatrixAlgorithm(s).minStep());
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }
    }}class MatrixFactory {
    private MatrixFactory() {
        //
    }
    
    public static String[] nextMatrix() {
        List<String> list = new ArrayList<String>();
        Scanner sc = new Scanner(System.in);
        try {
            System.out.println("Please input an 8 digits string which composed with the number of [1-8].");
            System.out.println("Type [00000000] to end the input.");
            while (true) {
                System.out.print("input:");
                String s = sc.nextLine();
                if ("00000000".equals(s)) {
                    break;
                }
                list.add(s);
            }
        } catch (Throwable e) {
            e.printStackTrace();
        } finally {
            sc.close();
        }
        
        return list.toArray(new String[0]);
    }
}class MatrixAlgorithm {
    static final int MAX_ROW = 2;
    static final int MAX_COL = 4;
    static final char[][] ORIGINAL_MATRIX = {{'1', '2', '3', '4'}, {'8', '7', '6', '5'}};
    static final MatrixOrder[] MATRIX_ORDERS = {new MatrixOrderA(), new MatrixOrderB(), new MatrixOrderC()};
    static List<Integer> routeList = new ArrayList<Integer>();
    
    private char[][] matrix = new char[2][0];
    private Character[][] matrixCopy;
    private boolean available = true;
    
    public MatrixAlgorithm(String source) {
        available = validate(source);
        if (available) {
            matrix[0] = source.substring(0, 4).toCharArray();
            matrix[1] = source.substring(4, 8).toCharArray();
            getMatrixCopy();
        }
    }
    
    public int minStep() {
        if (available == false) {
            return -1;
        }
        if (matchOriginal(matrixCopy)) {
            return 0;
        }
        
        if (routeList.isEmpty()) {
            getAllRoute();
        }
        int min=0, step=0;
        boolean first = true;
        for (Integer route : routeList) {
            step = getStep(getMatrixCopy(), route);
            if (first) {
                min = step;
                first = false;
            } else if (min > step) {
                min = step;
            }
        }
        
        return (min > 8 ? -1 : min);
    }
    
    private boolean validate(String source) {
        if (source.isEmpty()) {
            return false;
        } else if (source.matches("^\\d{8}?$")) {
            boolean f = true;
            for (int i=1; i<9; i++) {
                if (source.length() - source.replaceAll(""+i, "").length() != 1) {
                    f = false;
                    break;
                }
            }
            return f;
        } else {
            return false;
        }
    }
    
    private Character[][] getMatrixCopy() {
        if (matrixCopy == null) {
            matrixCopy = new Character[2][4];
        }
        for (int i=0; i<MAX_ROW; i++) {
            for (int j=0; j<MAX_COL; j++) {
                matrixCopy[i][j] = matrix[i][j];
            }
        }
        return matrixCopy;
    }
    
    private boolean matchOriginal(Character[][] c) {
        boolean f = true;
        for (int i=0; i<MAX_ROW; i++) {
            for (int j=0; j<MAX_COL; j++) {
                if (c[i][j] != ORIGINAL_MATRIX[i][j]) {
                    f = false;
                    break;
                }
            }
        }
        return f;
    }
    
    private int getStep(Character[][] c, int route) {
        int step = 0;
        
        while (route > 0) {
            step++;
            MATRIX_ORDERS[(route%10)-1].changeOrder(c, MAX_ROW, MAX_COL);
            if (matchOriginal(c)) {
                return step;
            }
            route /= 10;
        }
        
        step++;
        return step;
    }
    
    private void getAllRoute() {
        int[] tmp = new int[8];
        for (int i=0; i<tmp.length; i++) {
            tmp[i] = 1;
        }
        routeList.add(11111111);
        int route=0;
        while (true) {
            tmp[tmp.length-1]++;
            for (int i=tmp.length-1; i>0; i--) {
                if (tmp[i] > 3) {
                    tmp[i] = 1;
                    tmp[i-1]++;
                }
            }
            route = toInt(tmp);
            if (route > 33333333) {
                break;
            }
            routeList.add(route);
        }
    }
    
    private int toInt(int[] a) {
        int sum=0, digit=1;
        for (int i=a.length-1; i>=0; i--) {
            sum += digit*a[i];
            digit *= 10;
        }
        return sum;
    }
}abstract class MatrixOrder {
    public<T> boolean isAvailableMatrix(T[][] matrix, int rows, int cols) {
        if (matrix.length != rows) {
            return false;
        }
        for (int i=0; i<rows; i++) {
            if (matrix[i].length != cols) {
                return false;
            }
        }
        return true;
    }
    
    public<T> T[][] changeOrder(T[][] matrix, int rows, int cols) {
        if (isAvailableMatrix(matrix, rows, cols) == false) {
            return matrix;
        }
        
        return doChange(matrix, rows, cols);
    }
    
    abstract protected<T> T[][] doChange(T[][] matrix, int rows, int cols); 
}class MatrixOrderA extends MatrixOrder {
    @Override
    protected<T> T[][] doChange(T[][] matrix, int rows, int cols) {
        for (int i=0; i<rows-1; i++) {
            for (int j=0; j<cols; j++) {
                T t = matrix[i][j];
                matrix[i][j] = matrix[i+1][j];
                matrix[i+1][j] = t;
            }
        }
        return matrix;
    }
}class MatrixOrderB extends MatrixOrder {
    @Override
    protected<T> T[][] doChange(T[][] matrix, int rows, int cols) {
        for (int i=0; i<rows; i++) {
            T t = matrix[i][cols-1];
            for (int j=cols-1; j>0; j--) {
                matrix[i][j] = matrix[i][j-1];
            }
            matrix[i][0] = t;
        }
        return matrix;
    }
}class MatrixOrderC extends MatrixOrder {
    @Override
    protected<T> T[][] doChange(T[][] matrix, int rows, int cols) {
        if (cols < 3) {
            return matrix;
        }
        T t = matrix[0][cols-2];
        for (int i=cols-2; i>1; i--) {
            matrix[0][i] = matrix[0][i-1];
        }
        for (int i=0; i<rows-1; i++) {
            matrix[i][1] = matrix[i+1][1];
        }
        for (int i=1; i<cols-2; i++) {
            matrix[rows-1][i] = matrix[rows-1][i+1];
        }
        for (int i=rows-1; i>0; i--) {
            matrix[i][cols-2] = matrix[i-1][cols-2];
        }
        matrix[1][cols-2] = t;
        
        return matrix;
    }
}