好玩的游戏（蛙跳游戏的算法实现）

Question

    游戏规则如下：
    a和b分别代表两种青蛙，中间有一个空位格
    aaa bbb 
    最后青蛙要达到的状态：
    bbb aaa
    青蛙移动的规则：方向不能变，可以向前移一个格，或者是隔一个青蛙向前跳（类似“炮”）   
    例如：aaab bb aa babb
     
    欢迎喜欢思考的人，参与讨论。

Answer 1

这么巧啊，前几天朋友给我发来这个excel里的小游戏，说3分钟没搞出来智商就低于75
我3分钟没搞出来，很郁闷，就写了一个小程序
import java.util.Vector;public class move {
int[] frogs = { 1, 2, 3, 0, -1, -2, -3 };// >0表示公，小于0表示母 int emptyIndex = 3;// 空位置的index private Vector move = new Vector(); public static void main(String[] args) {
move m = new move();
m.jump(m.frogs);
} public void jump(int[] state) {
if (isSuccess(state)) {
printState();
return;
}
move.insertElementAt(state,move.size());
if (getPossibleMove(state).size() > 0) {
Vector v = getPossibleMove(state);
for (int i = 0; i < v.size(); i++) {
int[] possibleState = (int[]) v.get(i);
jump(possibleState);
}
move.removeElementAt(move.size() - 1); } else {
move.removeElementAt(move.size() - 1);
return;
}
} public void printState() {
for (int j = 0; j < move.size(); j++) {
int[] state = (int[]) move.get(j);
StringBuffer sb = new StringBuffer();
for (int i = 0; i < state.length; i++) {
if (state[i] > 0) {
sb.append("公青蛙" + (state[i]) + ",");
} else if (state[i] < 0) {
sb.append("母青蛙" + (-state[i]) + ",");
} else {
sb.append("空位,");
}
}
System.out.println(sb.toString());
}
System.out.println("成功");
} public boolean isSuccess(int[] state) {
if (state[0] < 0 && state[1] < 0 && state[2] < 0 && state[4] > 0
&& state[5] > 0 && state[6] > 0) {
return true;
}
return false;
} public void getEmptyIndex(int[] state) {
for (int i = 0; i < 7; i++) {
if (state[i] == 0) {
emptyIndex = i;
}
}
} public Vector getPossibleMove(int[] state) {// 得到所有可能的下一步状态
Vector v = new Vector();
getEmptyIndex(state);
for (int i = 0; i < frogs.length; i++) {
if (state[i] > 0) {// 公的只能向右，移动或跳格
if (i + 1 == emptyIndex) {
int[] stateTemp = new int[7];
System.arraycopy(state, 0, stateTemp, 0, 7);
stateTemp[i + 1] = state[i];
stateTemp[i] = 0;
v.add(stateTemp);
}
if (i + 2 == emptyIndex) {
int[] stateTemp = new int[7];
System.arraycopy(state, 0, stateTemp, 0, 7);
stateTemp[i + 2] = state[i];
stateTemp[i] = 0;
v.add(stateTemp);
}
} else if (state[i] < 0) {// 母的只能向左，移动或跳格
if (i - 1 == emptyIndex) {
int[] stateTemp = new int[7];
System.arraycopy(state, 0, stateTemp, 0, 7);
stateTemp[i - 1] = state[i];
stateTemp[i] = 0;
v.add(stateTemp);
}
if (i - 2 == emptyIndex) {
int[] stateTemp = new int[7];
System.arraycopy(state, 0, stateTemp, 0, 7);
stateTemp[i - 2] = state[i];
stateTemp[i] = 0;
v.add(stateTemp);
}
}
}
return v;
}}