4240074_ac_1485ms_4336k.java

北大大牛代码 1240道题的原代码 超级权威

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

//package pku2286;

import java.util.Scanner;

/**
 *
 * @author ZhaoJian
 */
public class Main {
    private Scanner in;
    
    private int limit;
    
    private int[] num = new int[25];
    
    private int[] ans;
    
    static final int[][][] mov = new int[8][][];

    static {
        mov[0] = new int[][] { {1,23}, {3,1}, {7,3}, {12,7}, {16,12}, {21,16}, {23,21} }; 
        mov[1] = new int[][] { {2,24}, {4,2}, {9,4}, {13,9}, {18,13}, {22,18}, {24,22} };
        mov[2] = new int[][] { {11,5}, {10,11}, {9,10}, {8,9}, {7,8}, {6,7}, {5,6} };
        mov[3] = new int[][] { {20,14}, {19,20}, {18,19}, {17,18}, {16,17}, {15,16}, {14,15} };
        mov[4] = new int[][] { {24,2}, {22,24}, {18,22}, {13,18}, {9,13}, {4,9}, {2,4} }; 
        mov[5] = new int[][] { {23,1}, {21,23}, {16,21}, {12,16}, {7,12}, {3,7}, {1,3} };
        mov[6] = new int[][] { {14,20}, {15,14}, {16,15}, {17,16}, {18,17}, {19,18}, {20,19} };
        mov[7] = new int[][] { {5,11}, {6,5}, {7,6}, {8,7}, {9,8}, {10,9}, {11,10} };

    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        new Main().run();
    }

    private int dfs(int depth) {
        int[] tmp = new int[25];
        
        if (depth == limit) {
            return ok();
        }
        if (depth + leastMove() > limit) {
            return 0;
        }
        for (int i = 0; i < 8; i++) {
            ans[depth] = i;
            
            System.arraycopy(num, 0, tmp, 0, 25);
            
            for (int j = 0; j < 7; j++) {
                num[mov[i][j][1]] = tmp[mov[i][j][0]];
            }
            
            int tmpvalue = dfs(depth + 1);
            
            System.arraycopy(tmp, 0, num, 0, 25);
            
            if (tmpvalue != 0) {
                return tmpvalue;
            }
        }
        return 0;
    }

    private int leastMove() {
        int[] cnt = new int[4];
        
        cnt[num[7]]++;cnt[num[8]]++;cnt[num[9]]++;
        cnt[num[12]]++;cnt[num[13]]++;
        cnt[num[16]]++;cnt[num[17]]++;cnt[num[18]]++;
        return 8 - Math.max(cnt[1], Math.max(cnt[2], cnt[3]));
    }

    private int ok() {
       
       int value = num[7];
       
       return (value == num[8] 
               && value == num[9]
               && value == num[12]
               && value == num[13]
               && value == num[16]
               && value == num[17]
               && value == num[18]) ? value : 0;
    }
    
    private void run() {
        
        in = new Scanner (System.in);
        
        while (true) {
            num[1] = in.nextInt();
            if (num[1] == 0) {
                break;
            }
            for (int i = 2; i <= 24; i++) {
                num[i] = in.nextInt();
            }
            if (ok() != 0) {
                System.out.println("No moves needed\n" + num[7]);
                continue;
            }
            int value = 0;
            for (limit = 1; ; limit++) {
                ans = new int[limit];
                value = dfs(0);
                if (value != 0) {
                    break;
                }
            }
            for (int i = 0; i < limit; i++) {
                System.out.print((char)('A' + ans[i]));
            }
            System.out.println("\n" + value);
            
        }
    }

}