起振兴中华
注意:不要提交解答过程,或其它辅助说明类的内容。
import java.util.*; import java.math.*; class State { int map[] = new int[8]; int step; int x = 0 , y = 0; public State(){} public State(State state) { setMap(state.map); step = state.step; x = state.x; y = state.y; } public void setMap(int Map[]) { for(int i = 0; i < 8; i++) map[i] = Map[i]; } } public class Main { //从我做起振兴中华 //1 2 3 45 6 7 8 static int map[][] = {{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}}; static int dir_x[] = {1,0,-1,0}; static int dir_y[] = {0,1,0,-1}; public static boolean bfs(State state, int dir) { int temp_x , temp_y; if(state.step > 8) return false; //出界 if(state.x+dir_x[dir] < 0 || state.x+dir_x[dir] >= 4) return false; if(state.y+dir_y[dir] < 0 || state.y+dir_y[dir] >= 5) return false; //继续前行 temp_x = state.x + dir_x[dir]; temp_y = state.y + dir_y[dir]; if(state.map[state.step-1] + 1 != map[temp_x][temp_y]) return false; state.x = temp_x; state.y = temp_y; state.map[state.step] = map[state.x][state.y]; state.step++; return true; } public static boolean isOk(State state) { int flag = 1; if(state.step != 8) return false; for(int i = 0; i < state.step - 1; i++) { if(state.map[i] != i+1) { flag = 0; break; } } if(flag == 1) return true; else return false; } public static void main(String[] args) { int count = 0; Queue<State>q = new LinkedList<State>(); //起始位置 State state = new State(); state.map[0] = 1; state.step = 1; q.add(state); while(!q.isEmpty()) { State temp1 = new State(); temp1 = q.remove(); if(isOk(temp1)) count++; for(int i = 0; i < 4; i++) { State temp2 = new State(temp1); if(bfs(temp2, i)) { q.add(temp2); } } } System.out.println(count); }//main() }//class Main
原文:http://blog.csdn.net/junwei_yu/article/details/21531911