2013
11-12

# 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.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main
{
private static Scanner        scan;
static
{
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>();
int[] array = new int[] { 0, 1, 2, 3, 4, 5, 6 };
String string = join(array);
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);
}
}
}
for (int i = 0; i < n; i++)
{
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();}.