本文主要是介绍小奇画画 （bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
红莲清泪两行欲吐半点却无
如初是你杳然若绯雾还在水榭畔画楼处
是谁衣白衫如初谁红裳如故
——《忆红莲》
小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）
输入
第一行包括1个整数n。
接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一个圆。
输出
输出一个整数表示答案。
样例输入
4 7 5 -9 11 11 9 0 20
样例输出
6
提示
对于 100%数据，1<=n<=300000,-10^9<=x<=10^9,1<=r<=10^9。
当某个圆被多个连续相切的小圆分成上下两部分时块数+2,其他情况块数+1。
上面的情况时最外面的圆被分成上下两部分所以+2，其他小圆每个+1，初始为1；
所以只需要判断有多少个+2的，最后再+圆的个数+1;
建图把每个大圆里直接包含的小圆建一条边，然后判断每个大圆直接相连的所有小圆的r的和是否等于大圆的r就可以
建图的话先按照左端点小-->大排序，左端点相等的话按右端点大-->小排序，然后用stack建图。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct node{ll x, r, left, right;
}a[300015];
vector<int> v[300015];
int sum[300015];
int cmp(node x, node y){if(x.left == y.left)return x.right > y.right;return x.left < y.left;
}int bfs(){queue<int> q;int ans = 0;for(int i = 0; i < n; i++){if(!sum[i]){q.push(i);}}while(!q.empty()){int u = q.front();q.pop();ll temp = 0;for(int i = 0; i < v[u].size(); i++){int e = v[u][i];temp += a[e].r;q.push(e);}if(temp == a[u].r)ans++;}return ans;
}int main()
{memset(sum,0,sizeof(sum));scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%lld%lld", &a[i].x, &a[i].r);a[i].left = a[i].x - a[i].r;a[i].right = a[i].x + a[i].r;}sort(a, a + n, cmp);stack<int> s;//建图for(int i = 0; i < n; i++){while(!s.empty()){int t = s.top();if(a[i].right <= a[t].right){v[t].push_back(i);sum[i]++;break;}s.pop();}s.push(i);}int ans = bfs() + 1 + n;printf("%d\n", ans);return 0;
}
这篇关于小奇画画 （bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
