要看视频效果在这里: https://www.douyin.com/video/7604003298768735540
场景：诺森德大陆，血色先锋军营地，巫妖王的"叛徒"正在向新来的亡灵小弟讲解业务...
小弟：（瑟瑟发抖）大、大哥，我听说咱们这次任务是要让血色十字军全军覆没？可我连他们营地的地图都看不懂啊...
你：（拍肩）放轻松，小骷髅。你看这张地图——5行4列，就是个Excel表格嘛！只不过填的不是数据，是"绝望"。
小弟：那两个发绿光的格子是啥？看着像发霉的面包...
你：那叫感染源！浅绿色标记的(1,1)和(5,4)，就是咱俩的"同事"——第0小时就已经中招的倒霉蛋。瘟疫从这里开始，向四周扩散，每小时感染一圈邻居。
小弟：哦...那黄色的格子呢？看着像黄油...
你：那是领主！大领主阿比迪斯的亲信，咱们的VIP客户。巫妖王说了，要精准掌握他们啥时候被感染，好安排"售后服务"。你看这三个黄油块——(2,4)、(3,3)、(5,3)，都是重点关照对象。
小弟：为啥有的格子写的数字值更大大而有的更小？
你：这就是最短感染时间！好比你在食堂排队，从两个窗口同时开饭，你当然会去人少的那个。瘟疫也一样聪明——它从两个感染源同时出发，哪个先到算哪个。比如中间那个格子，左上角的瘟疫要走3步，右下角的也要走3步，所以标3。
小弟：等等，为啥不一个一个感染源算，再取最小值？
你：（竖起骨指）问得好！这就是多源BFS的精髓！传统BFS像单口相声，一个人讲到底；多源BFS像群口相声，所有感染源同时开讲，谁先讲到算谁赢。咱们把所有感染源一次性塞进队列，让它们"齐头并进"，一圈一圈向外扩散。这样每个格子第一次被访问时，就是最短路径——哦不，最短感染时间！
小弟：队列？是那个排队买奶茶的数据结构吗？
你：对头！先进先出，公平得很。第0小时，队列里是俩感染源；第1小时，它们出队，把邻居塞进去；第2小时，邻居们再出队...像涟漪一样扩散。visited数组记着谁已经"领过盒饭"了，避免重复感染——咱们瘟疫也要讲效率，不养闲人。
小弟：我懂了！所以那个(2,4)的领主，数字是3，就是第3小时被感染？
你：聪明！你看C++精灵库多给力——黑底红字，绿色源头，黄色领主，动画一跑，BFS过程看得清清楚楚。要是没有这可视化，咱们还得在脑子里跑程序，那可比被圣骑士追着砍还难受！
小弟：（看着动画）哇，格子一个个变化，像在打节拍...
你：这就是算法的浪漫。记住，多源BFS的核心就一句话："众人拾柴火焰高，多源并进效率高"。不管是瘟疫传播、火灾蔓延，还是你同时从多个快递柜取包裹，都是这个理儿。
小弟：大哥，我还有个问题——如果两个感染源同时到达一个格子，算谁的？
你：（邪魅一笑）算先出队的那个！队列这玩意儿，虽然大家同时进，但总有先后顺序。不过时间一样，巫妖王才不在乎是谁的功劳呢，KPI达标就行。
小弟：最后那个
/* by 01130.hk - online tools website : 01130.hk/zh/calctemperature.html */ rocket.wait(1)是干啥的？让火箭等等我？你：那是让动画慢点跑，让你这迟钝的骨头能看清过程！不然一眨眼全感染完了，你还以为咱们开了挂。C++精灵库的
/* by 01130.hk - online tools website : 01130.hk/zh/calctemperature.html */ Sprite就像个听话的画师，指哪打哪，画格子、填颜色、写数字，全靠rocket这个角色跑腿。小弟：原来如此！感谢C++精灵库，让咱们亡灵也能搞算法可视化！
你：可不是嘛！要是没有这库，咱们就得写Windows API或者OpenGL，那复杂度...足以让巫妖王再死一次。现在几行代码就能看瘟疫扩散，简直是亡灵法师的福音！
小弟：（兴奋地搓手骨）我这就去向巫妖王汇报——三个领主分别在第3、3、1小时被感染！
你：（望向远方）去吧，记得告诉他——多源BFS，让背叛更高效。
技术总结（给活着的人看）
| 概念 | 解释 |
|---|---|
| 多源BFS | 多个起点同时入队，同步扩散，第一次访问即为最短距离 |
| 队列 | 保证按"时间顺序"处理，先进先出 |
| visited数组 | 防止重复访问，确保O(nm)时间复杂度 |
| C++精灵库 | 封装了图形渲染，让算法过程可视化，降低理解门槛 |
感谢C++精灵库，让我们能把抽象的队列操作变成直观的色彩流动，让算法不再枯燥，让背叛...啊不，让学习更加高效！
所有代码如下：
#include"sprites.h"//包含C++精灵库#include <queue>#include<algorithm>usingnamespacestd; Screen sc{"作者：李兴球"}; Sprite rocket;//建立角色叫rocket，画格子，写数字等用途intn=25,m=20,sidelen=25;//行，列，边长，示例里的5行，4列，边长设为100inta =3,b=4;//3个感染源，4个邻主，这里只进行演示，数据不需要输入，直接硬写。intlevel[502][502];//每个节点的层级，就最早感染时间intdirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//4个方向queue< pair<int,int> >q;boolvisited[502][502]; vector<pair<int,int>> lord;//保存几个领主的坐标vector<pair<int,int>> source;//保存几个感染源的坐标pair<int,int> convert_cors(introw,intcol){//坐标转换(0,0)左上角转换为真实坐标//srcx,srcy是单位坐标，sidelen是格子边长intx = sidelen*((n/2-row)) - (1-n%2)*sidelen/2;inty = (1-m%2)*sidelen/2-sidelen*((m/2-col));return{y,x}; }voiddraw_grid(intn,intm,intstep){//画格子图//行数，列数，格子边长，以原点画格子图intwidth = m*step,height=n*step; rocket.penup().go(-width/2,height/2).pd();for(inti=0;i<n;i++)rocket.fd(width).bk(width).addy(-step); rocket.penup().go(step-width/2,height/2).rt(90).pd();for(inti=1;i<m;i++)rocket.fd(height).bk(height).addx(step); rocket.fd(height).right(90).fd(width); }boolis_in_vector(pair<int,int> &cur,vector<pair<int,int> > &v){//cur是否在v向量中vector<pair<int,int>>::iterator it =find(v.begin(),v.end(),cur);returnit!=v.end(); }voidrender_grid(pair<int,int> &cur){//根据坐标类型不同渲染不同的背景色rocket.go(convert_cors(cur.first,cur.second));if(is_in_vector(cur,lord)) rocket.fill("yellow");elseif(is_in_vector(cur,source)) rocket.fill("light green"); rocket.write(to_string(level[cur.first][cur.second]),16); rocket.wait(0.01); }intmain(){//三位领主以黄色标记，每个节点感染时间就是它们的层级g_screen->bgcolor("black"); rocket.speed(0).color("gray").hide(); draw_grid(n,m,sidelen); rocket.penup().color("pink");//在第一行上面写数字序号for(intcol=1;col<=m;col++) rocket.go(convert_cors(-1,col-1)).write(to_string(col),16);//在第一列左边写数字序号for(introw=1;row<=n;row++) rocket.go(convert_cors(row-1,-1)).write(to_string(row),16); rocket.color("red");//格子里的层级数字用红色来写visited[0][0]=true; visited[14][3]=true; visited[20][19]=true;//标记感染源节点已被访问q.push({0,0}); q.push({14,3}); q.push({20,19});//三个感染源source.push_back({0,0}); source.push_back({14,3});//保存感染源source.push_back({20,19});//保存领主坐标lord.push_back({12,2}); lord.push_back({4,2}); lord.push_back({1,3}); lord.push_back({20,8}); lord.push_back({24,12}); lord.push_back({10,13});//开始进行多源BFS，即多个感染源扩散，这里才是核心代码while(!q.empty()){ pair<int,int> cur =q.front();q.pop(); render_grid(cur);//可视化渲染当前格子for(inti=0;i<4;i++){intnr = cur.first + dirs[i][0];//邻居行坐标intnc = cur.second + dirs[i][1];//邻居列坐标if(nr<0|| nr>=n || nc<0|| nc>=m)continue;//超出范围的忽略if(visited[nr][nc]==true)continue;//已访问过的节点忽略visited[nr][nc]=true; q.push({nr,nc});//入队level[nr][nc] = level[cur.first][cur.second] +1; } }for(pair<int,int>p:lord){introw = p.first,col =p.second; cout<< level[row][col] <<endl; } rocket.done(0);return0; }
