博客

【

题目

】

标题: 振兴中华

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。

地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）

从我做起振

我做起振兴

做起振兴中

起振兴中华

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

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

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

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

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

【

分析

】

本题的解题思想是通过递归思想遍历所有的可能情况，然后找出满足条件的答案。

【

源码

】

public class Test002 {
	
	private static char[][] a = {{'从','我','做','起','振'},
					      {'我','做','起','振','兴'},
					      {'做','起','振','兴','中'},
					      {'起','振','兴','中','华'}};
	
	private static int count; //计数变量

	public static void main(String[] args) {
		count = 0;
		char[] b = new char[8];
		jump(0, 0, 0, b);
		System.out.println(count);
	}
	
	/**
	 * 模拟小明跳跃格子的递归方法
	 * 
	 * @param step 跳格子经过的步数，范围是0-7
	 * @param x 向下跳的位置，范围是0-3
	 * @param y 向右跳的位置，范围是0-4
	 * @param b 暂存跳过路线的一维数组
	 */
	private static void jump(int step, int x, int y, char[] b){
		//*******递归出口**********
		if(x > 3){
			return;
		}
		
		if(y > 4){
			return;
		}
		
		if(step > 7){
			return;
		}
		
		//记录跳过的字
		b[step] = a[x][y];
				
		if(step == 7){
			//刚好走到8个字的位置
			if(check(b)){
				count++;
			}
			return;
		}
		
		jump(step+1, x+1, y, b); //向下跳
		jump(step+1, x, y+1, b); //向右跳
		
	}
	
	//检查数组内容是“从我做起振兴中华”
	private static boolean check(char[] b){
		if("从我做起振兴中华".equals(String.valueOf(b))){
			return true;
		}else{
			return false;
		}
	}
}

【

结果

】

35