首页 > 专题系列 > Java解POJ > POJ 3221 Diamond Puzzle [解题报告] Java
2013
11-12

POJ 3221 Diamond Puzzle [解题报告] Java

Diamond Puzzle

问题描述 :

A diamond puzzle is played on a tessellated hexagon like the one shown in Figure 1 below. And in this problem the faces produced by the tessellation are identified as they are numbered in the same figure. If two faces share a side, they are called neighboring faces. Thus, even-numbered faces have three neighboring faces, while odd-numbered faces have only two. At any point during the play of the puzzle, six of the seven faces hold a unique digit ranging from 1 to 6, and the other one is empty. A move in the puzzle is to move a digit from one face to a neighboring empty one.

Starting from any configuration, some series of moves can always make the puzzle look identical to either one shown in Figures 2 and 3. Your task is to calculate the minimum number of moves to make it become the one in Figure 2.

输入:

The input contains multiple test cases. The first contains an integer N (0 ≤ N ≤ 5,040), the number of test cases. Then follow N lines, each with a permutation of {0, 1, 2, 3, 4, 5, 6} describing a starting configuration of the puzzle. The ith digit in the permutation is the one in the face numbered i − 1. A zero means the face is empty.

输出:

For each test cases, output the minimum number of moves the configuration takes to reach the one shown in Figure 2. If this is impossible, just output “-1” and nothing else.

样例输入:

3
1324506
2410653
0123456

样例输出:

10
-1
0

解题代码:

//* @author: 
import java.io.BufferedReader;   
import java.io.InputStreamReader;   
import java.util.Arrays;   
import java.util.HashMap;   
import java.util.LinkedList;   
import java.util.Scanner;   
public class Main   
{   
    private static BufferedReader in;   
    private static Scanner        scan;   
    static  
    {   
        in = new BufferedReader(new InputStreamReader(System.in));   
        scan = new Scanner(in);   
    }   
    private static int[][]  move = new int[][] { { 2, 4, 6 }, { 2, 6 }, { 0, 1, 3 }, { 2, 4 },   
            { 0, 3, 5 }, { 4, 6 }, { 0, 1, 5 } };   
    public void run() throws Exception   
    {   
        HashMap< String, Integer> map = new HashMap< String, Integer>();   
        LinkedList< int[]> list = new LinkedList< int[]>();   
        LinkedList< String> listString = new LinkedList< String>();   
        int[] array = new int[] { 0, 1, 2, 3, 4, 5, 6 };   
        String string = join(array);   
        list.add(array);   
        listString.add(string);   
        map.put(string, 0);   
        while (!list.isEmpty())   
        {   
            array = list.pop();   
            string = listString.pop();   
            int index = 0;   
            for (; array[index] != 0; index++);   
            for (int newIndex : move[index])   
            {   
                int[] newArray = array.clone();   
                int tmp = newArray[index];   
                newArray[index] = newArray[newIndex];   
                newArray[newIndex] = tmp;   
                String newString = join(newArray);   
                if (!map.containsKey(newString))   
                {   
                    map.put(newString, map.get(string) + 1);   
                    list.add(newArray);   
                    listString.add(newString);   
                }   
            }   
        }   
        int n = Integer.parseInt(in.readLine());   
        for (int i = 0; i < n; i++)   
        {   
            String str = in.readLine().trim();   
            if (map.containsKey(str))   
            {   
                System.out.println(map.get(str));   
            }   
            else  
            {   
                System.out.println(-1);   
            }   
        }   
    }   
    private String join(int[] array)   
    {   
        StringBuilder buffer = new StringBuilder();   
        for (int i : array)   
        {   
            buffer.append(i);   
        }   
        return buffer.toString();   
    }   
    public static void main(String[] args) throws Exception   
    {   
        new Main().run();   
    }   
}

  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.