CraneWork

/*Problem Statement
There are three stacks of crates - two of them outside of the warehouse, and one inside the warehouse.
We have a crane that can move one crate at a time, and we would like to move all of the crates to the stack inside the warehouse.
A heavier crate can never be stacked on top of a lighter crate, and all three initial stacks obey that rule.
Create a class CraneWork that contains a method moves that is given int[]s stack1, stack2, and warehouse containing the initial three stacks,
and returns the minimum number of moves required to move all the crates into the warehouse stack.
The elements of stack1, stack2, and warehouse represent the weights of the crates and are given from top to bottom
(and thus in non-decreasing order of weight).

Definition
Class: CraneWork
Method: moves
Parameters: int[], int[], int[]
Returns: int
Method signature: int moves(int[] stack1, int[] stack2, int[] warehouse)
(be sure your method is public)

Constraints
stack1, stack2, and warehouse will each contain between 0 and 20 elements, inclusive.
The total number of elements in the three stacks will be between 1 and 20, inclusive.
Each element in the three stacks will be between 1 and 200, inclusive.
stack1, stack2, and warehouse will each be in non-decreasing order.

Examples

0){3,50} {} {1,2,50,50,50}
Returns: 12
Move 3 to stack2, 1 to stack1,
2 to stack2, 1 to stack2,
50 to warehouse, 1 to warehouse,
2 to stack1, 1 to stack1,
3 to warehouse, 1 to stack2,
2 to warehouse, 1 to warehouse.

1){50} {50} {10,20,30}
Returns: 17
Start by moving 50 from stack2 to stack1.
It then takes 7 moves to transfer the 10,20,30
to stack 2, 2 moves to transfer the 2 50's to the warehouse,
and 7 more to transfer the 10,20,30 to the warehouse.

2){} {} {2,5,6,7}
Returns: 0
All the crates are already in the warehouse.

3){1,2,3} {} {}
Returns: 7
Move 1 from stack1 to warehouse, 2 from stack1 to stack2,
1 from warehouse to stack2, 3 from stack1 to warehouse,
1 from stack2 to stack1, 2 from stack2 to warehouse, 1 from stack1 to warehouse.

This problem statement is the exclusive and proprietary property of TopCoder, Inc.
Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc.
is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. */

package cranework_2;

public class CraneWork {

public static void moves(int[] stack_1, int[] stack_2, int[] ware_house) throws Exception{
CrateStack stack1 = new CrateStack(stack_1);
CrateStack stack2 = new CrateStack(stack_2);
CrateStack warehouse = new CrateStack(ware_house);

show(stack1, stack2, warehouse);
moves(stack1, 0, stack2, 0, warehouse, 0);
}

/**
* @param stack1
* @param cursor1
* @param stack2
* @param cursor2
* @param stack3
* @param cursor3
* @throws Exception
*/
public static void moves(CrateStack stack1, int cursor1, CrateStack stack2, int cursor2, CrateStack stack3, int cursor3) throws Exception{

if(cursor1 == stack1.root && cursor2 == stack2.root) return;

if(cursor1 == stack1.root) {
if(cursor3 == stack3.root) {
moves(stack2, cursor2 + 1, stack3, stack3.root, stack1, stack1.root);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
} else if (stack2.getValue(cursor2) > stack3.getValue(cursor3)) {
moves(stack2, cursor2 + 1, stack3, cursor3, stack1, stack1.root);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
}else {
cursor3 = stack3.find(stack2.getValue(cursor2));

moves(stack2, cursor2 + 1, stack3, cursor3, stack1, stack1.root);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
}
} else if(cursor2 == stack2.root) {
if(cursor3 == stack3.root) {
moves(stack1, cursor1 + 1, stack3, stack3.root, stack2, stack2.root);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
} else if (stack1.getValue(cursor1) > stack3.getValue(cursor3)) {
moves(stack1, cursor1 + 1, stack3, cursor3, stack2, stack2.root);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
}else {
cursor3 = stack3.find(stack1.getValue(cursor1));

moves(stack1, cursor1 + 1, stack3, cursor3, stack2, stack2.root);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
}
} else if(cursor3 == stack3.root) {
if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) {
moves(stack1, cursor1 + 1, stack3, stack3.root, stack2, cursor2);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
} else {
moves(stack2, cursor2 + 1, stack3, stack3.root, stack1, cursor1);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
}
} else if (stack3.getValue(cursor3) > stack2.getValue(cursor2) && stack3.getValue(cursor3) > stack1.getValue(cursor1)) {
if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) {

cursor3 = stack3.find(stack1.getValue(cursor1));

moves(stack1, cursor1 + 1, stack3, cursor3, stack2, cursor2);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
} else {
cursor3 = stack3.find(stack2.getValue(cursor2));

moves(stack2, cursor2 + 1, stack3, cursor3, stack1, cursor1);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
}
} else {
if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) {
moves(stack1, cursor1 + 1, stack3, cursor3, stack2, cursor2);

stack3.pushCrate(stack1.popCrate());

show(stack1, stack2, stack3);

moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root);
}
else {
moves(stack2, cursor2 + 1, stack3, cursor3, stack1, cursor1);

stack3.pushCrate(stack2.popCrate());

show(stack1, stack2, stack3);

moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root);
}
}
}

public static void show(CrateStack stack1, CrateStack stack2, CrateStack stack3){
System.out.println("Round:");
stack1.showStack();
stack2.showStack();
stack3.showStack();
//System.out.print("\n " + cursor1.weight + " " + cursor2.weight + " " + cursor3.weight);
System.out.println("\n");
}
}

class CrateStack {

private int[] stack = new int[20];

public int root = 0;

public CrateStack(int weight) {
stack[0] = weight;
root++;
}

public CrateStack(int[] array) {
for(int i = 0; i < array.length; i++) {
stack[i] = array[i];
}
root = array.length;
}

//Push a Value into Stack
public void pushCrate(int value) {
stack[root] = value;
root++;
}

//Pop a Value into Stack
public int popCrate() throws Exception{
if(root != 0) {
root--;
int result = stack[root];
stack[root] = 0;
return result;
}
throw new NullPointerException();
}


public boolean isTop(int cursor) {
if(cursor == root - 1) return true;
return false;
}

public void showStack() {
try {
if (root == 0) {
System.out.print("{}");
} else {
int temp = root - 1;
System.out.print("{");
while (temp >= 0) {
System.out.print(stack[temp] + ",");
temp--;
}
System.out.print("}");
}
} catch (Exception e) {
//
}
}

public int find (int temp) {
int cursor = 0;
if (temp != 0) {
while(cursor != root) {
if (stack[cursor] < temp) return cursor;
cursor++;
}
}

return root;
}

public int getValue(int index) {
return stack[index];
}

}


遗憾的是如果有重量相同的情况还没有解决。

评论

1 楼 mabusyao 2012-02-17  

某位同学给我提供的堪称完美的解决方案：

1. 将三个int数组放在一起排序，生成这样一个char数组[A,B,C,C,C,A,B,B,A].
2. 简单的move方法

	private static void move(char[] stack, int index, char to) {
		if (index == 0) {
			if (stack[index] == to) {
				// Do nothing.
			} else {
				System.out.println("move stack from " + stack[0] + " to " + to);
				stack[0] = to;
			}

			return;
		} else {
			if (stack[index] == to) {
				move(stack, index - 1, to);
			} else {
				move(stack, index - 1, getMidum(stack[index], to));

				System.out.println("move stack from " + stack[index] + " to "
						+ to);
				stack[index] = to;

				move(stack, index - 1, to);
			}

		}
	}

经测试可行，且为最优解