洛谷p1332血色先锋队的amp；quot；瘟疫传播指南amp；quot；_多源BFS，让背叛更高效。

#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; }