C++递归（2）

数塔问题？

题目描述： 有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

输入 输入数据首先包括一个整数整数N(1 输出 从底层走到顶层经过的数字的最大和是多少？

输入复制

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出复制

30

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110];
int ma=-1;
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<i+1;j++){cin>>a[i][j];}}func(0,0,0);cout<<ma;return 0;
}
void func(int x,int y,int sum)
{if(x==n){sum=sum+a[x][y];ma=max(ma,sum);return;}func(x+1,y,sum+a[x][y]);func(x+1,y+1,sum+a[x][y]);
}

摘花生问题

题目描述： Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来 到一片有网格状道路的矩形花生地(如下图)

从西北 角进去，东南角出来。地里每个道路的交叉点上都 有种着一株花生苗，上面有若干颗花生，经过一株 花生苗就能摘走该它上面所有的花生。Hello Kitty只 能向东或向南走，不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。

如输入：

2 2

1 1

3 4

代表有2行，每行有2株花生，那么摘能摘到的最多的花生就是： 1>>3>>4 = 8，总和为8颗花生。

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110];
int ma=-1;
int n,m;
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}func(0,0,0);cout<<ma;return 0;
}
void func(int x,int y,int sum)
{if(x==n&&y==m){sum=sum+a[x][y];ma=max(ma,sum);return;}if(x!=n){func(x+1,y,sum+a[x][y]);}if(y!=m){func(x,y+1,sum+a[x][y]);}
}

卒过河

题目描述： A 点有一个过河卒，需要走到目标 B 点。

卒行走规则：可以向下、或者向右。

同时在棋盘上的任一点有一个对方的马（如图的C 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如图中 C 点可以控制 9 个点（图中的P1，P2 … P8 和 C） 。

卒不能通过对方马的控制点。

棋盘用坐标表示，现给定A 点位置为（0,0）B 点位置为（n,m）(n,m 为不超过 10 的整数)，马的 位置为C（X,Y）（约定: C点与A点不重叠，与B点也不重叠）。要求你计算出卒从 A 点能够到达 B 点的路径的条数。

样例

输入复制

6 6 3 2

输出复制

17

输入 B点的坐标（n,m）以及对方马的坐标（X,Y） （马的坐标一定在棋盘范围内，但要注意，可 能落在边界的轴上） 输出 到达b点的路径条数

#include<bits/stdc++.h>
using namespace std;
void func(int,int);
int a[110][110]={0};
int cnt=0;
int n,m;
int u,v;
int main()
{cin>>n>>m;cin>>u>>v;a[u][v]=1;a[u-2][v-1]=1;a[u-2][v+1]=1;a[u+2][v-1]=1;a[u+2][v+1]=1;a[u-1][v-2]=1;a[u+1][v-2]=1;a[u-1][v+2]=1;a[u+1][v+2]=1;func(0,0);cout<<cnt;return 0;
}
void func(int x,int y)
{if(a[x][y]==1){return;}if(x==n&&y==m){cnt++;return;}if(x!=n){func(x+1,y);}if(y!=m){func(x,y+1);}
}

流感传染

题目描述： 有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为 一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得 了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不 变），空房间不会传染。请输出第m天得流感的人数。 输入 第一行一个数字n，n不超过100，表示有n*n的宿舍房间。 接下来的n行，每行n个字符，‘ . ’表示第一天该房间住着健康的人，’#’表示该 房间空着，’@’表示第一天该房间住着得流感的人。 接下来的一行是一个整数m，m不超过100. 输出 输出第m天，得流感的人数

样例输入

5

. . . .#

.#.@.

.#@. .

#. . . .

. . . . .

4

样例输出

16