青蛙跳的问题.

Question

有7个位置和6只青蛙.
A1 A2 A3 0 B1 B2 B3
A系列的青蛙可以向右跳.但不能回跳(向左跳)
B系列的青蛙可以向左跳.也不能回跳.(向右跳)如果A系列的右边是0,则可以向右跳.如
A1 A2 0 A3 B1 B2 B3
同理B系列左边是0,则可以向左跳.如
A1 A2 A3 B1 0 B2 B3如果青蛙可以越过某青蛙跳,比如从初始状态通过这种跃跳可以变成以下情况:
A1 0 A3 A2 B1 B2 B3
A2越过A3跳到了0的位置...最终状态为了跳到如下情况
B1 B2 B3 0 A1 A2 A3
就是A B系列的青蛙互换.
嗯.各位达人先不要骂我自己不思考.是能力有限..暂时只能想到如下的思路.从初始状态遍历.找到有0的位置.正负2内看是否有青蛙.如果有就交换位置.
然后将交换后的情况放入树里.之后生成下一个状态.
比如从初始状态开始就有四种情况.
A1 A2 0  A3 B1 B2 B3
A1 A2 A3 B1 0  B2 B3
A1 0  A3 A2 B1 B2 B3
A1 A2 A3 B2 B1 0  B3如果遇到进行不下去而又不是最终状态.则终止这个树节点.返回上个节点..现在的问题是.如何生成下一个状态.返回一个状态很好弄.如何返回n个状态呢?
还有就是终止某个不能进行下去的节点之后.如何返回上个节点并进行其它的(嗯.这个貌似已经有点想通了..)麻烦各位达人帮忙提点一下.如果有代码.最好能有说明.谢谢各位了...
已经写了的一些代码:
package jump;public class JumpTest
{
public static void main(String[] agrs)
{
int num[] = JumpTest.initStart();


while(!(JumpTest.endToStart(num)))
{

} }

//判断是否为最终状态
public static boolean endToStart(int[] num)
{
int[] endNum = JumpTest.initEnd();
boolean result = false;
for(int i =0;i<num.length;i++)
{
if(num[i]!=endNum[i])
{
result = false;
break;
}
else
{
result = true;
}
}
return result;
}
//初始化最终状态
public static int[] initEnd()
{
int MAX=7;
int num[] = new int[MAX];
for(int i=0;i<MAX/2;i++)
{
num[i]=(-1);
}
num[MAX/2] = 0;

for(int j=(MAX/2)+1;j<MAX;j++)
{
num[j] = (1);
}

return num;
}
//初始化开始状态
public static int[] initStart()
{
int MAX=7;
int num[] = new int[MAX];
for(int i=0;i<MAX/2;i++)
{
num[i]=1;
}
num[MAX/2] = 0;

for(int j=(MAX/2)+1;j<MAX;j++)
{
num[j] = (-1);
}

return num;

}}
package jump;import java.util.ArrayList;public class Node
{
public Node parent = null; public ArrayList childrenList = new ArrayList(); public int[] value; boolean isRoot = false; public Node()
{ } public Node(int[] value)
{
this.value = value;
} public void addChild(Node child)
{
childrenList.add(child);
} public Node getChild(int index)
{
return (Node) childrenList.get(index);
} public int getChildCount()
{
return childrenList.size();
} public int getDepth()
{
if (isRoot())
return 0;
else
return 1 + getParent().getDepth();
} public boolean isInternalNode()
{
if (childrenList != null)
return true;
else
return false;
} public boolean isLeaf()
{
if (childrenList == null)
return true;
else
return false;
} public boolean isRoot()
{
return isRoot;
} public void removeChildAt(int index)
{
childrenList.remove(index);
} public void setRoot()
{
isRoot = true;
} public Node getParent()
{
return parent;
} public void setParent(Node parent)
{
this.parent = parent;
} public ArrayList getChildrenList()
{
return childrenList;
}
}

Answer 1

呵呵..谢谢两位的回复T_T
自己顶一下T_T

Answer 2

类似8皇后问题，用回溯应该可以解决。
偶的思路是这样的：
//定义一个stack记录状态
//把初始值push到stack中
//while(未穷尽[stack.size()>0]){
//  if(可走且此走步发未发生过){
//    跳
//    if(是最终结果){
//      退出
//    }else{
//      记录走步
//      记录本次状态stack.push(...)
//    }
//  }else{
//    返回前次状态stack.pop()
//  }
//}实际写的时候要考虑多得多。很伤脑筋的事，没有写的欲望。

Answer 3

感谢一下楼上的:)
不过那个 未穷尽[stack.size()>0是什么意思呢?

Answer 4

参看
http://community.csdn.net/Expert/TopicView3.asp?id=4822363我以前正好写过，发出来给大家参考import java.util.Vector;public class move {
int[] frogs = { 1, 2, 3, 0, -1, -2, -3 };// >0表示公，小于0表示母int emptyIndex = 3;// 空位置的indexprivate 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;
}}
最后结果是：
公青蛙1,公青蛙2,公青蛙3,空位,母青蛙1,母青蛙2,母青蛙3,公青蛙1,公青蛙2,空位,公青蛙3,母青蛙1,母青蛙2,母青蛙3,公青蛙1,公青蛙2,母青蛙1,公青蛙3,空位,母青蛙2,母青蛙3,公青蛙1,公青蛙2,母青蛙1,公青蛙3,母青蛙2,空位,母青蛙3,公青蛙1,公青蛙2,母青蛙1,空位,母青蛙2,公青蛙3,母青蛙3,公青蛙1,空位,母青蛙1,公青蛙2,母青蛙2,公青蛙3,母青蛙3,空位,公青蛙1,母青蛙1,公青蛙2,母青蛙2,公青蛙3,母青蛙3,母青蛙1,公青蛙1,空位,公青蛙2,母青蛙2,公青蛙3,母青蛙3,母青蛙1,公青蛙1,母青蛙2,公青蛙2,空位,公青蛙3,母青蛙3,母青蛙1,公青蛙1,母青蛙2,公青蛙2,母青蛙3,公青蛙3,空位,母青蛙1,公青蛙1,母青蛙2,公青蛙2,母青蛙3,空位,公青蛙3,母青蛙1,公青蛙1,母青蛙2,空位,母青蛙3,公青蛙2,公青蛙3,母青蛙1,空位,母青蛙2,公青蛙1,母青蛙3,公青蛙2,公青蛙3,母青蛙1,母青蛙2,空位,公青蛙1,母青蛙3,公青蛙2,公青蛙3,母青蛙1,母青蛙2,母青蛙3,公青蛙1,空位,公青蛙2,公青蛙3,成功公青蛙1,公青蛙2,公青蛙3,空位,母青蛙1,母青蛙2,母青蛙3,公青蛙1,公青蛙2,公青蛙3,母青蛙1,空位,母青蛙2,母青蛙3,公青蛙1,公青蛙2,空位,母青蛙1,公青蛙3,母青蛙2,母青蛙3,公青蛙1,空位,公青蛙2,母青蛙1,公青蛙3,母青蛙2,母青蛙3,公青蛙1,母青蛙1,公青蛙2,空位,公青蛙3,母青蛙2,母青蛙3,公青蛙1,母青蛙1,公青蛙2,母青蛙2,公青蛙3,空位,母青蛙3,公青蛙1,母青蛙1,公青蛙2,母青蛙2,公青蛙3,母青蛙3,空位,公青蛙1,母青蛙1,公青蛙2,母青蛙2,空位,母青蛙3,公青蛙3,公青蛙1,母青蛙1,空位,母青蛙2,公青蛙2,母青蛙3,公青蛙3,空位,母青蛙1,公青蛙1,母青蛙2,公青蛙2,母青蛙3,公青蛙3,母青蛙1,空位,公青蛙1,母青蛙2,公青蛙2,母青蛙3,公青蛙3,母青蛙1,母青蛙2,公青蛙1,空位,公青蛙2,母青蛙3,公青蛙3,母青蛙1,母青蛙2,公青蛙1,母青蛙3,公青蛙2,空位,公青蛙3,母青蛙1,母青蛙2,公青蛙1,母青蛙3,空位,公青蛙2,公青蛙3,母青蛙1,母青蛙2,空位,母青蛙3,公青蛙1,公青蛙2,公青蛙3,成功

Answer 5

注释不详细，但是思路和楼上卡西提的一样，只不过我用vector实现出栈入栈