本文涉及知识点

C++BFS算法

LeetCode2101. 引爆最多的炸弹

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。
示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。
示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。
示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：

• 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
• 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
• 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
  所以总共有 5 个炸弹被引爆。

C++BFS

一：建立临接表。两枚炸弹中心的距离d1小于等于两者半径r1,r2，则会引爆。r1能引爆r2，不意味者r2能引爆r1，也就是有向图。时间复杂度：O(nn)。为了避免处理误差，可以比较d1$\times$d1 和 r1$\times$ r1。
二，枚举引爆各炸弹，枚举炸弹的时间复杂度O(n)，BFS每枚炸弹的范围O(nn)。总时间复杂度：O(nnn)。
BFS的初始状态：leves[0] = {root}。
BFS的状态：leves[i]记录 爆炸i轮后被引爆的炸弹。
BFS的后续状态：通过next访问cur的临接表。
BFS的返回值：vis中true的数量。
BFS的出重：bool向量v出重。
可直接求各点级别，然后统计级别大于等于0。

代码

核心代码

class CBFSLeve {
public :
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]]+1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
};

class Solution {
		public:
			int maximumDetonation(vector<vector<int>>& bombs) {
				m_c = bombs.size();
				vector<vector<int>> neiBo(m_c);
				auto Is = [](vector<int>& p1, vector<int>& p2) {
					return ((long long)p1[0] - p2[0]) * ((long long)p1[0] - p2[0]) + ((long long)p1[1] - p2[1]) * ((long long)p1[1] - p2[1]) <= (long long)p1[2] * p1[2];
				};
				for (int i = 0; i < bombs.size(); i++) {
					for (int j = 0; j < bombs.size(); j++) {
						if (Is(bombs[i], bombs[j])) {
							neiBo[i].emplace_back(j);
						}
					}
				}
				int ret = 1;
				for (int i = 0; i < m_c; i++) {
					auto leves = CBFSLeve::Leve(neiBo, { i });
					const int cur = std::count_if(leves.begin(), leves.end(), [&](const int& d1) {return d1 >= 0 ; });
					ret = max(ret, cur);
				}
				return ret;
			}
			int m_c;
		};

单元测试

	vector<vector<int>> bombs;
		TEST_METHOD(TestMethod1)
		{
			bombs = { {0,0,1},{3,3,1} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod2)
		{
			bombs = { {0,0,1} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod3)
		{
			bombs = { {1,1,10000} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		} 
		TEST_METHOD(TestMethod4)
		{
			bombs = { {1,1,10000},{100000, 100000, 1} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod5)
		{
			bombs = { {0,0,3},{3, 4, 4} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod11)
		{
			bombs = { {2,1,3},{6,1,4} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 2);
		}
		TEST_METHOD(TestMethod12)
		{
			bombs = { {1,1,5},{10,10,5} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod13)
		{
			bombs = { {1,2,3},{2,3,1},{3,4,2},{4,5,3},{5,6,4} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 5);
		}
		TEST_METHOD(TestMethod14)
		{
			bombs = { {54,95,4},{99,46,3},{29,21,3},{96,72,8},{49,43,3},{11,20,3},{2,57,1},{69,51,7},{97,1,10},{85,45,2},{38,47,1},{83,75,3},{65,59,3},{33,4,1},{32,10,2},{20,97,8},{35,37,3} };
			auto res = Solution().maximumDetonation(bombs);
			AssertEx(res, 1);
		}