Problem 洛谷P2845-Switching on the Lights 开关灯
Accept: 154 Submit: 499
Time Limit: 1000 mSec Memory Limit : 128MB
Problem Description
Farm John 最近新建了一批巨大的牛棚。这些牛棚构成了一个N*N的矩形网络。(1<n<100)
然而bessie十分怕黑,他想计算可以把多少个牛棚的灯打开。
有N*N个房间,组成了一张N*N的网格图,Bessie一开始位于左上角(1,1),并且只能上下左右行走。
一开始,只有(1,1)这个房间的灯是亮着的,Bessie只能在亮着灯的房间里活动。
有另外M条信息,每条信息包含四个数a,b,c,d,表示房间(a,b)里有房间(c,d)的灯的开关。
请计算出最多有多少个房间的灯可以被打开。
Input
第一行,两个数:N,M(1<m<200000);
第2-m+1行:坐标(x1,y1),(x2,y2)代表房间的坐标(x1,y1)及可以点亮的·房间的坐标(x2,y2);
Output
一个数,最多可以点亮的房间数
Sample Input
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
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1
Sample Output
5
题目链接:https://www.luogu.org/problemnew/show/P2845
题解:乍一看这个题觉得这个题咋这么水,凉了之后画了个稍微大一点图,意识到用普通的广搜的话,会有一些点会被误判为不能到的点而只是点亮而不进队,这样就很明显有问题了。
解决方案其实挺好想的,把原来的vis数组变成vis和illu数组,前者用来标记到过没有,后者标记点亮没有,新到一个房间,有一些它能打开的灯,对于这些点,判断它的四周有没有之前到过的点,
如果有,那它也能到,入队。当然了,判断当前房间四周有没有开灯是必然的。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std; const int maxn = +,maxm = +; bool vis[maxn][maxn];
bool illu[maxn][maxn];
int n,m;
int tot,head[maxn*maxn];
int dir[][] = {{,},{,},{-,},{,-}}; struct Point{
int x,y;
Point(int x = ,int y = ) :
x(x),y(y) {}
}; struct Edge{
int to,next;
Edge(int to = ,int next = ) :
to(to),next(next) {}
}edge[maxm]; void AddEdge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}; inline void cal(int v,int &x,int &y){
if(v%n == ){
x = v/n,y = n;
}
else x = v/n+,y = v%n;
} inline bool Judge(int x,int y){
if(<=x && <=y && x<=n && y<=n) return true;
return false;
} void BFS(){
queue<Point> que;
que.push(Point(,));
vis[][] = illu[][] = true;
while(!que.empty()){
Point first = que.front();
que.pop();
int u = (first.x-)*n+first.y;
for(int k = ;k < ;k++){
int xx = first.x+dir[k][],yy = first.y+dir[k][];
if(Judge(xx,yy)){
if(!vis[xx][yy] && illu[xx][yy]){
vis[xx][yy] = true;
que.push(Point(xx,yy));
}
}
}
for(int i = head[u];i != -;i = edge[i].next){
int v = edge[i].to;
int x,y;
cal(v,x,y);
illu[x][y] = true;
if(!vis[x][y]){
for(int k = ;k < ;k++){
int xx = x+dir[k][],yy = y+dir[k][];
if(Judge(xx,yy) && vis[xx][yy]){
vis[x][y] = true;
que.push(Point(x,y));
}
}
}
}
}
} int main()
{
//freopen("input.txt","r",stdin);
memset(vis,false,sizeof(vis));
memset(illu,false,sizeof(illu));
memset(head,-,sizeof(head));
tot = ;
scanf("%d%d",&n,&m);
int a,b,c,d;
for(int i = ;i <= m;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
int u = (a-)*n+b,v = (c-)*n+d;
AddEdge(u,v);
}
BFS();
int ans = ;
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
if(illu[i][j]) ans++;
}
}
printf("%d\n",ans);
return ;
}