题解：洛谷 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(1<N≤100,1<M<2×105)。

第2 ∼ M + 1 2 \sim M + 12∼M+1行，每行输入四个整数( 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-二维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=105,M=200005;intn,m,ans;// n: 网格大小，m: 开关数量，ans: 亮灯数量vector<PII>sw[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偏移queue<PII>q;// 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(intj=0;j<4;j++){intnnx=nx+dx[j],nny=ny+dy[j];// 相邻位置// 检查边界if(nnx<1||nnx>n||nny<1||nny>n)continue;// 如果相邻位置已访问过，则将新亮的灯加入队列if(vis[nnx][nny]){vis[nx][ny]=1;// 标记新亮的灯已访问q.push({nx,ny});// 入队break;// 找到一个即可}}}}// 遍历当前位置的四个相邻位置for(inti=0;i<4;i++){intnx=x+dx[i],ny=y+dy[i];// 相邻位置// 检查边界、是否访问过、灯是否亮着if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]||!lights[nx][ny])continue;vis[nx][ny]=true;// 标记已访问q.push({nx,ny});// 入队}}}intmain(){cin>>n>>m;// 输入网格大小和开关数量while(m--)// 读入所有开关信息{inta,b,c,d;cin>>a>>b>>c>>d;// (a,b)处的开关控制(c,d)处的灯sw[a][b].push_back({c,d});}bfs();// 执行BFS// 统计亮着的灯的数量for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(lights[i][j])ans++;cout<<ans<<endl;// 输出结果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