首页 > 2021绿皮书笔试技术类公共题目-编程题讲解-dfs
头像
晗江雪
编辑于 2021-09-08 10:50
+ 关注

2021绿皮书笔试技术类公共题目-编程题讲解-dfs

练习题1:三国鼎立

【题目描述】

在n∗m的棋盘格状土地上盘踞着三个国家的若干股势力,上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道,土地上总共有多少股势力?

输入描述:

第一行两个正整数,土地宽n,长m;

接下来一个n∗m个矩阵,今包含'1'、'2'、'3',表示土地上的国家分布。

输出描述:

一个正整数,势力股数。

备注:

1≤n、w≤100。

输入样例:

4 4

1122

1222

3111

3333

输出样例:

4

说明:

11

1

是1国的一块势力

22

222

是2国一块势力

3

3333

是3国一块势力

111

是1国的另一块势力

总共4块势力


点击链接查看视频讲解与线上OJ练习

https://www.nowcoder.com/link/book2021-72212



练习题2:小美的送花线路

【题目描述】

小美是美团的一名鲜花快递员,鲜花是一种保质期非常短的商品,所以需要尽快送到客户手中,公司对于骑手的一个要求就是要规划送花的线路,使得骑手送完所有订单走的路程尽可能少。(骑手开始派送时带走了所有需要派送的花,不必每单后返回花店,路程结算是从花店出发,到送完最后一名客户为止,不计算从最后一名客户家回到花店的时间)

公司对于骑手的绩效评价是取决于两个指标,一是从花店到所有客户地址的距离之和,另一个是骑手实际走的路程。

设花店始终位于1号位置,客户共有n-1个,其编号为2~n。令dis(i,j)表示i号位置到j号位置的距离,即分别计算,和骑手实际所走的最短路程。

为了简化问题,我们约束这n个位置构成的是一棵树,即只有n-1条边在其中互相连接,且保证n个点彼此连通。

输入描述:

输出第一行包含一个正整数n,即花店和客户的总数。(1≤n≤30000)

接下来有n-1行,每行有三个整数u,v,w,表示在u和v之间存在一条距离为w的道路。(1≤w≤1000)

输出描述:

输出包含两个整数,中间用空格隔开,分别表示花店到所有客户地址的距离之和和骑手实际走的路程。

输入样例:

5

1 2 3

1 3 1

1 4 2

2 5 1

输出样例:

10 10


点击链接查看视频讲解与线上OJ练习

https://www.nowcoder.com/link/book2021-72213



完整绿皮书纸质版免费领取:

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐