标题: 振兴中华

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

地上画着一些格子,每个格子里写一个字,如下所示:

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

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

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

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

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

思路:dfs枚举,用1-8来代替汉字

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<string.h>
using namespace std;

int arr[4][5] = {{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}};
int stack[8]={0};
int isv[4][5] = {0};
int cnt = 0;

int check(){
for(int i = 0; i < 8; ++i){
if(stack[i] != i+1) return 0;
else continue;
}
return 1;
}

void dfs(int i, int j,int index){
if(i>=4 || i<0 || j<0 || j>=5) return;
if(isv[i][j]) return;
if(index > 8) return;

if(index == 8){
if(check()){
cnt++;
return;
}
}

stack[index] = arr[i][j];
isv[i][j] = 1;

++index;
dfs(i+1,j,index);
dfs(i,j+1,index);
dfs(i-1,j,index);
dfs(i,j-1,index);

isv[i][j] = 0;
--index;
}


int main(){
dfs(0,0,0);
cout<<cnt<<endl;
return 0;
}
//Prints:35