1、毒草的入侵
一份自定义大小的草坪，其中有三种土地形式，普通草，毒草，石头。第零个星期， 毒草只有一颗。每个星期，毒草会传播到已被毒草占领的格子四面八方的每一个没有石头 的格(包括垂直与水平相邻的和对角线上相邻的格)。1 周之后，这些新占领的格又可以把 毒草传播到更多的格里面了。
草地由一个图片表示。”.”表示草，而”*”表示大石头。比如这个 X=4, Y=3 的例子。
....
..*.
.**.
如果毒草一开始在左下角(第 1 排，第 1 列)，那么草地的地图将会以如下态势发展:.... .... MMM. MMMM MMMM ..*. MM*. MM*. MM*M MM*M M**. M**. M**. M**. M**M
星期数 0 1 2 3 4 毒草会在 4 星期后占领整片土地。
输入
4 3 1 1 (土地大小和毒草起始位置) .... ..*. .**.
输出 4 星期
涉及知识 :BFS 或 DFS 算法
#include//结构体 点struct node{ int x, y;}q[1000];char a[1000][1000];int vis[1000][1000];int xx[10] = {-1,0,1,-1,1,-1,0,1};int yy[10] = {-1,-1,-1,0,0,1,1,1};int m, n, x, y, head, tail, mx;void Scanf(void);void bfs(int, int);int isValid(int, int);void Push(int, int);int main(){ Scanf(); bfs(x,y); printf("%d星期",mx-1); return 0;}//读入数据//入口参数：无//返回：无void Scanf(void){ int i, j; scanf("%d%d%d%d",&m, &n, &x, &y); for (i = 1; i <= n; i++) { getchar(); for (j = 1; j <=m; j++) scanf("%c", &a[i][j]); }}//bfs//入口参数：起始坐标//返回：无void bfs(int x,int y){ int i, hx, hy; Push(x,y); vis[x][y] = 1; while (head <= tail) { hx = q[++head].x; hy = q[head].y; for (i = 0; i < 8; i++) if (isValid(hx+xx[i],hy+yy[i])) { Push(hx+xx[i],hy+yy[i]); vis[hx+xx[i]][hy+yy[i]] = vis[hx][hy] + 1; if (vis[hx+xx[i]][hy+yy[i]] > mx) mx = vis[hx+xx[i]][hy+yy[i]]; } }}//向队列q中添加点//入口参数：坐标//返回：无void Push(int x,int y){ q[++tail].x = x; q[tail].y = y;}//判断点是否有效//入口参数：坐标//返回：1或0int isValid(int x, int y){ if (x>0 && x<=n & y>0 && y<=m) if (a[x][y] == '.' && !vis[x][y]) return 1; return 0;}
2、最大子树和
一株奇怪的花卉，上面共连有 N 朵花，共有 N-1 条枝干将花儿连在一起，并且未修剪时每 朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美 丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为:去掉其中的一条 枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一 株花(也可能是一朵)。老师的任务就是:通过一系列“修剪”(也可以什么“修剪”都 不进行)，使剩下的那株(那朵)花卉上所有花朵的“美丽指数”之和最大。第一行 第一行输入 N 朵花 第二行输入每朵花的美丽指数 输出最大美丽指数和
邻接表存储
#include//结构体 边struct Edge{ int to,next;}e[1000];int val[1000];int head[1000];int cnt, flag = 0;void ins(int, int);void dp(int);int max(int, int);int main(){ int n, i, mx; scanf("%d",&n); for (i = 1; i <= n; i++) { scanf("%d",&val[i]); if (val[i] >=0) flag = 1; } if (flag == 1) { for (i = n; i > 1; i--) ins(i/2,i); dp(1); } mx = val[1]; for (i = 1; i <= n; i++) { if (val[i] > mx) mx = val[i]; } printf("%d",mx); return 0;}//加边u->v//入口参数：起点终点//返回：无void ins(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt;}//求以x为根二叉树的最大值//入口参数：节点x//返回：无void dp(int x){ int v, i; for (i = head[x]; i; i = e[i].next) { v = e[i].to; dp(v); val[x] = max(val[x],val[x] + val[v]); } if (val[x] < 0) val[x] = 0;}//求最大值//入口参数：变量x,y//返回：最大值int max(int x, int y){ if (x>y) return x; return y;}
二维数组存储
#includeint val[1000];int ch[1000][2];void Build(int);int max(int, int, int, int, int);int main(){ int n, i, mx, flag = 0;//flag = 0，全为负数 scanf("%d",&n); for (i = 1; i <= n; i++) { scanf("%d",&val[i]); if (val[i] > 0) flag = 1; } Build(n); if (flag == 1) { for (i = n/2; i>=1; i--) { val[i] = max(val[i],val[i] + val[ch[i][0]],val[i] + val[ch[i][1]], val[i] + val[ch[i][0]] + val[ch[i][1]], 0); } } mx = val[1]; for (i = 1; i < n ; i++) if (val[i] > mx) mx = val[i]; printf("%d",mx); return 0;}//建立二叉树//入口参数：节点数量//返回：无void Build(int n){ int i; for (i = 1; 2*i+1 <= n; i++) { ch[i][0] = 2*i; ch[i][1] = 2*i+1; } if (n%2 == 0) ch[n/2][0] = n;}//求最大值//入口参数：变量//返回：最大值int max(int x1, int x2, int x3, int x4, int x5){ int t = x1; if (x2 > t) t = x2; if (x3 > t) t = x3; if (x4 > t) t = x4; if (x5 > t) t = x5; return t;}