振兴中华

起振兴中华

注意：不要提交解答过程，或其它辅助说明类的内容。

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

振兴中华,布布扣,bubuko.com

振兴中华

原文：http://blog.csdn.net/junwei_yu/article/details/21531911