振兴中华

欢迎访问我的新博客：http://www.milkcu.com/blog/

原文地址：http://www.milkcu.com/blog/archives/1395367620.html

引言

这是2013年蓝桥杯软件大赛预赛A组（C/C++组）第3题，是个填空题，和深度优先搜索（DFS）有关，数路线和代码实现均较容易。

题目描述

标题: 振兴中华

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）

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

比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。

分析

由于数据规模比较小，可以不用编程实现，直接一条一条路线的数数。

比较好的方法是从上往下、从右往左的数，这样前面数过的路线刚好可以应用到后面的数数中。

1 = 1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15

所有路线加起来即可得到答案。

当然这题也可以使用深度优先实现，代码也很简单。

把“从我做起振兴中华”8个字替换为0~7的8个数字。

使用深度优先算法可以很方便的得出结果。

代码实现

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int map[4][5] = {{0, 1, 2, 3, 4},
                 {1, 2, 3, 4, 5},
                 {2, 3, 4, 5, 6},
				 {3, 4, 5, 6, 7}};
int cnt = 0;
int vis[4][5];
void dfs(int a, int b) {
	//cout << "dfs  " << a << "  " << b << endl;
	if(vis[a][b]) {
		return;
	}
	if(a == 3 && b == 4) {
		cnt++;
		return;
	}
	vis[a][b] = 1;
	for(int i = -1; i <= 1; i++) {
		for(int j = -1; j <= 1; j++) {
			if(i == j || abs(i) == abs(j)) {
				continue;
			}
			int newa = a + i;
			int newb = b + j;
			if(newa < 0 || newa >= 4 || newb < 0 || newb >= 5) {
				continue;
			}
			if(map[newa][newb] - map[a][b] == 1) {
				dfs(newa, newb);
			}
		}
	}
	vis[a][b] = 0;
}
int main(void) {
	memset(vis, 0, sizeof(vis));
	dfs(0, 0);
	cout << cnt << endl;
	return 0;
}

答案

（全文完）