题解：洛谷 P2845 [USACO15DEC] Switching on the Lights S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2845 [USACO15DEC] Switching on the Lights S - 洛谷【题目描述】有N × N N \times NN×N个房间组成了一张N × N N \times NN×N的网格图Bessie 一开始位于左上角( 1 , 1 ) (1,1)(1,1)并且只能上下左右行走。一开始只有( 1 , 1 ) (1,1)(1,1)这个房间的灯是亮着的Bessie 只能在亮着灯的房间里活动。有另外M MM条信息每条信息包含四个数a , b , c , d a,b,c,da,b,c,d表示房间( a , b ) (a,b)(a,b)里有房间( c , d ) (c,d)(c,d)的灯的开关。请计算出最多有多少个房间的灯可以被打开。【输入】第一行输入两个整数N , M ( 1 N ≤ 100 , 1 M 2 × 10 5 ) N,M(1 N \leq 100,1 M 2 \times 10 ^ 5)N,M(1N≤100,1M2×105)。第2 ∼ M 1 2 \sim M 12∼M1行每行输入四个整数( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2)(x1​,y1​),(x2​,y2​)代表房间的坐标( x 1 , y 1 ) (x_1,y_1)(x1​,y1​)可以点亮房间的坐标( x 2 , y 2 ) (x_2,y_2)(x2​,y2​)。【输出】一个数最多可以点亮的房间数。【输入样例】3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1【输出样例】5【算法标签】#普及plus #BFS-二维【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN105,M200005;intn,m,ans;// n: 网格大小m: 开关数量ans: 亮灯数量vectorPIIsw[N][N];// sw[x][y]: 位于(x,y)的开关控制的灯的位置列表boollights[N][N],vis[N][N];// lights: 灯是否亮着vis: BFS访问标记intdx[4]{-1,1,0,0};// 上下左右四个方向的x偏移intdy[4]{0,0,-1,1};// 上下左右四个方向的y偏移queuePIIq;// BFS队列// 广度优先搜索模拟灯的连锁点亮过程voidbfs(){q.push({1,1});// 从(1,1)开始lights[1][1]true;// (1,1)的灯初始亮着vis[1][1]true;// 标记(1,1)已访问while(!q.empty()){auto[x,y]q.front();// 取出队首位置q.pop();// 遍历当前位置开关控制的所有灯for(auto[nx,ny]:sw[x][y]){if(!lights[nx][ny])// 如果灯没亮{lights[nx][ny]true;// 点亮它// 检查这个新亮的灯周围是否有已访问过的灯for(intj0;j4;j){intnnxnxdx[j],nnynydy[j];// 相邻位置// 检查边界if(nnx1||nnxn||nny1||nnyn)continue;// 如果相邻位置已访问过则将新亮的灯加入队列if(vis[nnx][nny]){vis[nx][ny]1;// 标记新亮的灯已访问q.push({nx,ny});// 入队break;// 找到一个即可}}}}// 遍历当前位置的四个相邻位置for(inti0;i4;i){intnxxdx[i],nyydy[i];// 相邻位置// 检查边界、是否访问过、灯是否亮着if(nx1||nxn||ny1||nyn||vis[nx][ny]||!lights[nx][ny])continue;vis[nx][ny]true;// 标记已访问q.push({nx,ny});// 入队}}}intmain(){cinnm;// 输入网格大小和开关数量while(m--)// 读入所有开关信息{inta,b,c,d;cinabcd;// (a,b)处的开关控制(c,d)处的灯sw[a][b].push_back({c,d});}bfs();// 执行BFS// 统计亮着的灯的数量for(inti1;in;i)for(intj1;jn;j)if(lights[i][j])ans;coutansendl;// 输出结果return0;}【运行结果】3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1 5