洛谷P2845-Switching on the Lights 开关灯

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

Sample Output

题目链接：https://www.luogu.org/problemnew/show/P2845

题解：乍一看这个题觉得这个题咋这么水，凉了之后画了个稍微大一点图，意识到用普通的广搜的话，会有一些点会被误判为不能到的点而只是点亮而不进队，这样就很明显有问题了。

解决方案其实挺好想的，把原来的vis数组变成vis和illu数组，前者用来标记到过没有，后者标记点亮没有，新到一个房间，有一些它能打开的灯，对于这些点，判断它的四周有没有之前到过的点，

如果有，那它也能到，入队。当然了，判断当前房间四周有没有开灯是必然的。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int maxn = 100+10,maxm = 200000+10;
  9 
 10 bool vis[maxn][maxn];
 11 bool illu[maxn][maxn];
 12 int n,m;
 13 int tot,head[maxn*maxn];
 14 int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
 15 
 16 struct Point{
 17     int x,y;
 18     Point(int x = 0,int y = 0) :
 19         x(x),y(y) {}
 20 };
 21 
 22 struct Edge{
 23     int to,next;
 24     Edge(int to = 0,int next = 0) :
 25         to(to),next(next) {}
 26 }edge[maxm];
 27 
 28 void AddEdge(int u,int v){
 29     edge[tot].to = v;
 30     edge[tot].next = head[u];
 31     head[u] = tot++;
 32 };
 33 
 34 inline void cal(int v,int &x,int &y){
 35     if(v%n == 0){
 36         x = v/n,y = n;
 37     }
 38     else x = v/n+1,y = v%n;
 39 }
 40 
 41 inline bool Judge(int x,int y){
 42     if(1<=x && 1<=y && x<=n && y<=n) return true;
 43     return false;
 44 }
 45 
 46 void BFS(){
 47     queue<Point> que;
 48     que.push(Point(1,1));
 49     vis[1][1] = illu[1][1] = true;
 50     while(!que.empty()){
 51         Point first = que.front();
 52         que.pop();
 53         int u = (first.x-1)*n+first.y;
 54         for(int k = 0;k < 4;k++){
 55             int xx = first.x+dir[k][0],yy = first.y+dir[k][1];
 56             if(Judge(xx,yy)){
 57                 if(!vis[xx][yy] && illu[xx][yy]){
 58                     vis[xx][yy] = true;
 59                     que.push(Point(xx,yy));
 60                 }
 61             }
 62         }
 63         for(int i = head[u];i != -1;i = edge[i].next){
 64             int v = edge[i].to;
 65             int x,y;
 66             cal(v,x,y);
 67             illu[x][y] = true;
 68             if(!vis[x][y]){
 69                 for(int k = 0;k < 4;k++){
 70                     int xx = x+dir[k][0],yy = y+dir[k][1];
 71                     if(Judge(xx,yy) && vis[xx][yy]){
 72                         vis[x][y] = true;
 73                         que.push(Point(x,y));
 74                     }
 75                 }
 76             }
 77         }
 78     }
 79 }
 80 
 81 int main()
 82 {
 83     //freopen("input.txt","r",stdin);
 84     memset(vis,false,sizeof(vis));
 85     memset(illu,false,sizeof(illu));
 86     memset(head,-1,sizeof(head));
 87     tot = 1;
 88     scanf("%d%d",&n,&m);
 89     int a,b,c,d;
 90     for(int i = 1;i <= m;i++){
 91         scanf("%d%d%d%d",&a,&b,&c,&d);
 92         int u = (a-1)*n+b,v = (c-1)*n+d;
 93         AddEdge(u,v);
 94     }
 95     BFS();
 96     int ans = 0;
 97     for(int i = 1;i <= n;i++){
 98         for(int j = 1;j <= n;j++){
 99             if(illu[i][j]) ans++;
100         }
101     }
102     printf("%d
",ans);
103     return 0;
104 }