要看视频效果在这里: 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精灵库让我们能把抽象的队列操作变成直观的色彩流动让算法不再枯燥让背叛...啊不让学习更加高效所有代码如下#includesprites.h//包含C精灵库#include queue#includealgorithmusingnamespacestd; Screen sc{作者李兴球}; Sprite rocket;//建立角色叫rocket画格子写数字等用途intn25,m20,sidelen25;//行列边长示例里的5行4列边长设为100inta 3,b4;//3个感染源4个邻主这里只进行演示数据不需要输入直接硬写。intlevel[502][502];//每个节点的层级就最早感染时间intdirs[4][2] {{1,0},{-1,0},{0,1},{0,-1}};//4个方向queue pairint,int q;boolvisited[502][502]; vectorpairint,int lord;//保存几个领主的坐标vectorpairint,int source;//保存几个感染源的坐标pairint,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,heightn*step; rocket.penup().go(-width/2,height/2).pd();for(inti0;in;i)rocket.fd(width).bk(width).addy(-step); rocket.penup().go(step-width/2,height/2).rt(90).pd();for(inti1;im;i)rocket.fd(height).bk(height).addx(step); rocket.fd(height).right(90).fd(width); }boolis_in_vector(pairint,int cur,vectorpairint,int v){//cur是否在v向量中vectorpairint,int::iterator it find(v.begin(),v.end(),cur);returnit!v.end(); }voidrender_grid(pairint,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(intcol1;colm;col) rocket.go(convert_cors(-1,col-1)).write(to_string(col),16);//在第一列左边写数字序号for(introw1;rown;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()){ pairint,int cur q.front();q.pop(); render_grid(cur);//可视化渲染当前格子for(inti0;i4;i){intnr cur.first dirs[i][0];//邻居行坐标intnc cur.second dirs[i][1];//邻居列坐标if(nr0|| nrn || nc0|| ncm)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(pairint,intp:lord){introw p.first,col p.second; cout level[row][col] endl; } rocket.done(0);return0; }