首页 > 其他 > 详细

振兴中华

时间:2014-03-19 15:34:53      阅读:402      评论:0      收藏:0      [点我收藏+]
标题: 振兴中华
    小明参加了学校的趣味运动会,其中的一个项目是:跳格子。

    地上画着一些格子,每个格子里写一个字,如下所示:(也可参见p1.jpg)

从我做起振
我做起振兴
做起振兴中

起振兴中华

bubuko.com,布布扣


    比赛时,先站在左上角的写着“从”字的格子里,可以横向或纵向跳到相邻的格子里,但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

    要求跳过的路线刚好构成“从我做起振兴中华”这句话。

    请你帮助小明算一算他一共有多少种可能的跳跃路线呢?

答案是一个整数,请通过浏览器直接提交该数字。

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



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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!