第三课《病毒扩散实验室——层级 BFS》一、故事开始危险的病毒1.砰一个危险的病毒储存罐炸了2、病毒开始扩散而且每分钟都会向四周蔓延3、算法国王问❓“最快要多久会感染扩散到王宫”4、算法大臣说“这可以使用 BFS 来看一下”二、今天要学什么1、前两课我们已经学会✅ BFS 会一层层扩散✅ BFS 可以求最短路✅ 二维迷宫 BFS2、今天我们要真正理解“层”的概念3、因为BFS 的核心就是“层”三、什么叫“层”1、假设病毒起点在中间。2、初始地图. . . . V . . . .3、这里V 病毒源头4、第0层病毒刚出现第0分钟5、第1层1分钟后上下左右感染. V . V V V . V .6、第2层继续扩散V V V V V V V V V7、你发现了吗病毒是一圈一圈扩散的这就是 BFS 的层四、BFS 为什么能求最短路1、因为1第0层0步到达2第1层1步到达3第2层2步到达4第3层3步到达所以2、BFS 的层数就是最短距离这是今天最重要的一个结论五、多个起点怎么办1、前两课只有一个起点。例如S2、但今天可能有多个病毒源头3、例如V . . . . . . . V4、病毒会同时扩散5、这叫多源 BFS六、多源 BFS 的核心思想其实非常简单1、把所有起点一起入队1例如q.push({0,0}); q.push({2,2});2于是两个病毒一起扩散。七、层级 BFS 是我们的帮手1、掌握这个特性是高手和新手的分界线2、有的同学只会背 BFS 模板。但不知道“层”到底怎么控制。3、今天我们要掌握层级 BFS的技巧八、队列分层技巧1、核心代码int sz q.size();2、什么意思表示当前这一层一共有多少个点3、例如队列里A B C4、说明这一层有3个位置。5、处理完这3个后所有下一批进入队列的就是下一层九、层级 BFS 的完整过程1、第0层队列V处理完后加入四周位置2、第1层再处理这些位置。于是一层一层扩散十、经典病毒感染题1、题目地图V . . . # . . . .规则2、每分钟病毒向上下左右扩散。3、墙壁#不能穿过。4、问几分钟感染整个地图十一、完整程序#include iostream #include queue using namespace std; struct Node { int x; int y; }; char mp[105][105]; bool vis[105][105]; int dx[4] {-1,1,0,0}; int dy[4] {0,0,-1,1}; int main() { int n 3; int m 3; char temp[3][3] { {V,.,.}, {.,#,.}, {.,.,.} }; // 复制地图 for(int i 0; i n; i) { for(int j 0; j m; j) { mp[i][j] temp[i][j]; } } queueNode q; // 找病毒起点 for(int i 0; i n; i) { for(int j 0; j m; j) { if(mp[i][j] V) { q.push({i,j}); vis[i][j] true; } } } int minute 0; while(!q.empty()) { int sz q.size(); // 当前层 for(int i 0; i sz; i) { Node cur q.front(); q.pop(); int x cur.x; int y cur.y; for(int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if(nx 0 nx n ny 0 ny m !vis[nx][ny] mp[nx][ny] ! #) { vis[nx][ny] true; q.push({nx, ny}); } } } // 扩散完一层 minute; } cout 感染完成用了 minute - 1 分钟 endl; return 0; }十二、程序执行过程1、第0分钟V . . . # . . . .2、第1分钟V V . V # . . . .3、第2分钟V V V V # . V . .4、继续……5、最终全部感染。十三、为什么 minute 要最后加初学同学这里会晕1、因为我们是一层处理完才过去1分钟2、不是处理一个点就1。十四、多源 BFS 的真正本质1、普通 BFS一个起点扩散2、多源 BFS多个起点同时扩散3、本质上还是 BFS十五、什么时候想到“层级 BFS”以后看到1、病毒传播2、火焰蔓延3、洪水扩散4、消息传播5、⏰最少时间扩散可以想到BFS十六、课堂挑战题 ⚔️挑战1地图V . . . . # . . . . . V问几分钟感染全地图挑战2如果病毒还能斜着传播怎么办提示方向数组改成八方向挑战3如果有的人2分钟后才会被感染怎么办提示加入队列还要看他的感染发作时间。十七、本课最终总结1、BFS 的本质一层一层扩散2、BFS 的层数就是最短距离3、⏰层级 BFS一层 一分钟4、多源 BFS多个起点一起扩散5、队列分层技巧int sz q.size();今天真正学会的不只是病毒题。而是掌握“时间扩散模型”。
