jiugong.rar

import java.util.*; public class jiugong{ public static boolean BFS(state s0,state s1){ Queue <state> open=new LinkedList<state>(); Stack <state> closed=new Stack<state> (); open.offer(s0); state s=new state(s0); state ns; int flag=0; while(!open.isEmpty()){ s=open.poll(); //s.print(); closed.push(s); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } break; } } if(flag==1){ flag=0; break; } } } return false; } public static boolean DFS(state s0,state s1){ Stack <state> open=new Stack<state> (); Stack <state> closed=new Stack<state> (); s0.depth=0; s0.parent=null; open.push(s0); state s; state ns; int flag=0; int maxDepth=4; while(!open.isEmpty()){ s=open.pop(); if(s.depth>maxDepth){ continue; } // s.print(); closed.push(s); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } break; } } if(flag==1){ flag=0; break; } } } return false; } public static boolean GPS(state s0,state s1){ ArrayList <state> open=new ArrayList <state>(); Stack <state> closed=new Stack <state>(); s0.depth=0; s0.parent=null; s0.value=state.different(s0,s1)+s0.depth; open.add(s0); state s; state ns; int flag=0; while(!open.isEmpty()){ s=open.get(0); open.remove(0); closed.push(s); // s.print(); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } break; } } if(flag==1){ flag=0; break; } } state.sort(open); } return false; } public static void main(String [] args) { int num0[][]={{1,3,4},{8,2,0},{7,6,5}}; state state0=new state(num0); int numn[][]={{1,2,3},{8,0,4},{7,6,5}}; state state1=new state(numn); //BFS(state0,state1); //DFS(state0,state1); GPS(state0,state1); } }