中石油训练赛 - Bee Problem(dfs+连通块)

题目描述

You are a busy little bee, and you have a problem. After collecting nectar all day long, you are returning to the beehive with a large supply of honey. You would really like to take a nap now, but sadly, you have to store all the honey in your beehive first. Opening up a cell in the hive to funnel honey into takes a lot of time, so you want to avoid doing this as much as possible.
Some of the cells in the beehive are already filled with old, hardened honey. The other cells are still empty. If you pour honey into an empty cell, it will automatically start flowing into adjacent empty cells. From these cells, the honey will again flow to other neighbouring empty cells. This saves you from having to funnel honey into them directly. You decide to use this to your advantage, by pouring into cells with lots of (indirect) adjacent open cells.

figure 1: The beehives from the first two samples. The black hexagons already contain hardened honey. The white cells are still empty.
You have some units of honey, and know the layout of your beehive. By cleverly choosing which cells to funnel honey into, what is the minimal amount of work you have to do?

 

输入

• The input starts with three integers, 0 ≤ h ≤ 106, the amount of honey you have, and 1 ≤ n, m ≤ 103, the dimensions of the grid.
• Then follow n lines, one for each row of the grid. Each row has m symbols, either .,representing an empty cell, or #, representing a filled cell. These symbols are separated by spaces. Furthermore, every second row starts with a space, as these are slightly offset to the right.
The grid always has enough open cells to store all your honey.

 

输出

Output a single integer, the number of cells you have to funnel honey into directly to store all your honey in the hive.

 

样例输入

复制样例数据

8 4 4 . # # .# . # . # # # .# . . .

样例输出

3

题目链接：点击查看

---

题目大意：给出一个h表示现在身上的蜂蜜数量，再给出一个蜂巢的结构图，黑色表示已经满了，白色表示是空着的，每个小格子互相都是连通的，我们可以将身上的蜂蜜往小格子中填充，问若要将身上的蜂蜜都填充到蜂巢中，最少需要对几个小格子操作

题目分析：emmmm，我知道我的语文很差，题意可能没说清楚，不过转换一下，这就是一个让求最大连通块的问题，只不过这个问题有两个方面需要注意一下，第一就是我们需要将所有的连通块都求出来，然后对每个连通块进行降序排序，因为这个题目中的dfs是边搜边更新的，所以每个点至多遍历一次，时间复杂度也就控制在了n*m之内，这样就不用担心递归会超时的问题了，第二个方面就是这个题目中，不像中规中矩的那种矩形一样是上下左右走的，而是每个点有6个方向可以走，而奇数行和偶数行的方向又有那么一点点不同，所以我们一共设置12个方向，分别供奇数行和偶数行的点来使用，这个画个图就能推出来6个节点的编号，这里不赘述了

然后还有一个小坑，就是在输入的时候，题目每个节点之间都有一个空格，十分的恶心人，而且偶数行的开头还会有一个前置空格，我们在输入的时候要记着用getchar读掉，或者可以直接用cin，可以略过空格直接读到符号，cin大法好嗷，还有一点，这个题目多组输入会TLE，我人当时就傻了，可能还是我太菜了吧555

上代码吧：

#include<iostream> #include<algorithm> using namespace std;const int N=1e3+100;char maze[N][N];int ans[N*N];int cnt;int h,n,m;const int b1[6][2]={0,1,0,-1,1,0,-1,0,-1,-1,1,-1};//jiconst int b2[6][2]={0,1,0,-1,1,0,-1,0,1,1,-1,1};//ouint num;void dfs(int x,int y) {num++;maze[x][y]='#';for(int k=0;k<6;k++){int xx,yy;if(x&1){xx=x+b2[k][0];yy=y+b2[k][1];}else{xx=x+b1[k][0];yy=y+b1[k][1];}if(xx<0||yy<0||xx>=n||yy>=m)continue;if(maze[xx][yy]=='#')continue;dfs(xx,yy);} }bool cmp(int a,int b) {return a>b; }int main() {scanf("%d%d%d",&h,&n,&m);cnt=0;getchar();for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>maze[i][j];for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(maze[i][j]=='.'){num=0;dfs(i,j);ans[cnt++]=num;}}sort(ans,ans+cnt,cmp); // for(int i=0;i<cnt;i++) // cout<<ans[i]<<' '; // cout<<endl;int temp=0;int tem=0;int t=0;while(tem<h&&t<cnt){temp++;tem+=ans[t++];}cout<<temp<<endl;return 0; }

 

总结

以上是生活随笔为你收集整理的中石油训练赛 - Bee Problem(dfs+连通块)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。