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 <stdio.h>
//结构体 点
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或0
int 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 <stdio.h>
//结构体 边
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;
}
二维数组存储
#include <stdio.h>
int 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;
}
转载于:https://www.cnblogs.com/liumengyue/p/10032159.html