第四届蓝桥杯软件类省赛真题-C-A-3_振兴中华

//第四届蓝桥杯软件类省赛真题-C-A-3_振兴中华.cpp
/*
【题目】
标题: 振兴中华
小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）
从我做起振
我做起振兴
做起振兴中
起振兴中华
比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，
但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
*/
/*【解题思路】
解法：深度优先搜索
答案：
35
*/
#include<iostream>
using namespace std;
//此变量用于表示格子地图，其中，值为0表示"从"，值为1表示"我"，值为2表示"做"，
//值为3表示"起"，值为4表示"振"，值为5表示"兴"，值为6表示"中"，值为7表示"华"，
int map[4][5] = {
{0,1,2,3,4},
{1,2,3,4,5},
{2,3,4,5,6},
{3,4,5,6,7}
};
bool visit[4][5];//用于表示格子是否被走过
//此变量用于下一步走法的计算
int next[4][2] = {
{-1,0},//向上走
{1,0},//向下走
{0,-1},//向左走
{0,1},//向右走
};
int count = 0;
void dfs(int x,int y,int step)
{
//到达终点，计数加1
if(x ==3 && y == 4){
count++;
return;
}
//上下左右走
for(int i = 0;i<4;i++){
int tx = x+next[i][0];//下一步走法的横坐标x
int ty = y+next[i][1];//下一步走法的纵坐标y
//判断是否越界，越界则跳出此次循环,执行下一次循环
if(tx<0 || tx > 3 || ty<0 || ty >4)
continue;
//如果下一步满足条件可走，则递归走下一步
if(visit[tx][ty] == false && map[tx][ty] == step+1){
visit[tx][ty] = true;
dfs(tx,ty,step+1);//递归走下一步
visit[tx][ty] = false;
}
}
return;
}
int main()
{
visit[0][0] = true;
dfs(0,0,0);
cout<<"小明他一共有
"<<count<<"
种可能的跳跃路线";
return 0;
}

最后

以上就是彩色黑夜为你收集整理的第四届蓝桥杯软件类省赛真题-C-A-3_振兴中华的全部内容，希望文章能够帮你解决第四届蓝桥杯软件类省赛真题-C-A-3_振兴中华所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。