题解 | Switching-牛客假日团队赛4H题

H-Switching on the Lights_牛客假日团队赛4

https://ac.nowcoder.com/acm/contest/947/H

题目描述

Farmer John has recently built an enormous barn consisting of an $N×N$ grid of rooms $(2≤N≤100)$ , numbered from $(1,1)$ up to $(N,N)$ . Being somewhat afraid of the dark, Bessie the cow wants to turn on the lights in as many rooms as possible.

Bessie starts in room $(1,1)$ , the only room that is initially lit. In some rooms, she will find light switches that she can use to toggle the lights in other rooms; for example there might be a switch in room $(1,1)$ that toggles the lights in room $(1,2)$ . Bessie can only travel through lit rooms, and she can only move from a room $(x,y)$ to its four adjacent neighbors $(x−1,y), (x+1,y)$ , $(x,y−1)$ and $(x,y+1)$ (or possibly fewer neighbors if this room is on the boundary of the grid).

Please determine the maximum number of rooms Bessie can illuminate.

输入描述:

The first line of input contains integers $N$ and $M (1≤M≤20,000)$ .

The next MM lines each describe a single light switch with four integers $x, y, a, b,$ that a switch in room $(x,y)$ can be used to toggle the lights in room $(a,b)$ . Multiple switches may exist in any room, and multiple switches may toggle the lights of any room.

输出描述:

A single line giving the maximum number of rooms Bessie can illuminate.

示例1

输入

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

说明

Here, Bessie can use the switch in $(1,1)$ to turn on lights in $(1,2)$ and $(1,3)$ . She can then walk to $(1,3)$ and turn on the lights in $(2,1)$ , from which she can turn on the lights in $(2,2)$ . The switch in $(2,3)$ is inaccessible to her, being in an unlit room. She can therefore illuminate at most 5 rooms.

解答

初看这道题，感觉就是一道搜索题，于是乎，立马有思路了：不断对原图进行搜索（BFS），碰到了房间就把该房间可以打开的灯全部打开，直到某一次搜索过后我们没有打开任何一盏灯为止。

这个思路是没有问题的，然而~~常识告诉我们~~，这样做肯定会TLE，于是先考虑如何去优化这一个搜索的过程：

冷静分析，发现从第二次搜索开始，我们在搜索过程中事实上是搜到了一些重复的房间的，然而，很明显，因为我们曾经进到过这一个房间，并且将其能够打开的灯都打开了，所以再搜索这个房间是没有意义的。这就暗示我们：是不是可以通过某些操作来使得第二次搜索只会搜到有意义的房间呢？我们发现，一个房间是有意义的，当且仅当这个房间的灯被打开了并且我们曾经没有进到过这个房间里去。因此我们考虑使用一个数组（队列）记录在我当前这一次搜索中，打开了灯却不能走到的房间，然后下一次搜索的时候就只在这个队列里面进行搜索，这样，我们就可以保证每一个被打开了灯的房间只访问了一次。
于是，现在要解决的问题就是：何时停止搜索？我一开始写的是和最开始一样，这次搜索没有开过任何一盏灯时就结束，于是后来我调我wa了的程序调了一整天才发现这个错误。我们在优化时，把那些被打开了灯的房间记录下来是因为怕目前这个房间不能走到，而在我第一次搜索完，打开了更多的灯之后，有可能这个房间就能够走到了。而如果一个房间从原本的不可走到变成可以走到，说不定又会使得另一个房间由不可走到变成可走到。所以我们在面对一个房间，首先应该判断它在目前能不能够走到，如果可以走到，就打开它可以打开房间的灯。所以，搜索的终止条件应该是：在这一次搜索中，队列中的房间，没有任何一个房间可以被走到。这样就可以保证不漏解了。
到这里，事实上就已经可以在时限内得出答案了。但仔细思考过后，我们发现事实上还可以对目前的解法做一个小小的优化——降维。二维数组与一维数组的经验告诉我们，降维可以使得运算的时间更短一些。于是怎么降维呢？

我们发现：对于一个二维的地图，我们是用一个有序实数对 $（i，j）$ 来表示这个地图上的一个点，而事实上我们也可以将这个地图上的点从上到下，从左到右使用 $1\sim n^2$ 中的的数来表示这个地图上的每一个点

例如：

其中：黑框内为地图。

现在我们来说说在新的一维地图内如何进行搜索：

假设我们现在在map[i][j] (map[k])这个点

首先看看在二维地图中，我们搜索是向上、下、左、右走一步，分别对应

map【i-1】【j】,map【i+1】【j】,map【i】【j-1】,map【i】【j+1】；

而对于一维的地图，由于我们可以通过k=(i-1)*n+j这样的计算方式来将（i，j）映射成1~n^2里的每一个数，因此向上、下、左、右走就分别变对应：

map【k-n】,map【k+n】,map【k-1】,map【k+1】;

而这会导致一个bug，在k+1或k-1的时候：有可能跨行，如对于上面这个图，对于6这个点不加任何判断像上面这样遍历有可能会走到7这个点，而这样的操作是非法的，因此我们在遍历时就要加上一个特判（check函数），这样的话，应该就差不多没问题了吧。

到此为止：目前我能想到的优化就是这些了，于是，就上代码吧：、

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int MAXN=10001;//最多的点数 
int n,m,xx,yy,sp,ep,ans=1; 
int to[4];//方向数组 
int dl1[MAXN],head1=1,tail1=1; //BFS时用到的队列 
int dl2[MAXN],head2=1,tail2=1; //储存打开了灯目前却不能到达的房间的队列 
bool light_up[MAXN],vis[MAXN]; //灯是否已打开   是否这个点已经被访问过 
int indl[MAXN];                //每个点在哪个队列种（或是不在队列中） 
struct edge
{
    int v;
    edge *NEXT;
    edge() {v=0;NEXT=NULL;}
}*con[MAXN];                        //采用图的方式去存可以打开的灯的信息 
inline void ins(int start,int end)  //新的关系（加一条边） 
{
    edge *p=new(edge);
    p->v=end;
    p->NEXT=con[start];
    con[start]=p;
}
inline bool check(int nowplace)          //判断点是否能够到达 
{
    for(int i=0;i<4;++i)
    {
        int place=nowplace+to[i];
        if(place<1||place>n*n) continue;
        if(place%n==0&&to[i]==-1) continue;   //防bug 
        if(place%n==1&&to[i]==1) continue;    //防bug 
        if(vis[place]) return true;
    }
    return false;
}
inline void bfs()
{
    bool flag=false;      //判断是不是要再一次遍历 
    head2=tail2=1;   //另一个队列的初始化 
    while(head1<tail1)
    {
        int nv=dl1[head1++];indl[nv]=0;         //队首元素出队 
        if(check(nv)==false&&vis[nv]==false)    //判断目前这个房间能否被到达，或是本来就被到达过（主要是为了统一 1 这个点） 
            {dl2[tail2++]=nv;continue;}
        vis[nv]=true;flag=true;               //队列中有房间可以到达，可能会产生新的变化。 
        for(edge *p=con[nv];p;p=p->NEXT)
        {
            int vv=p->v;
            if(light_up[vv]==false)
                {light_up[vv]=true;++ans;}     //点亮关着灯的房间的灯 
            if(check(vv))                            //如果这个点能够被到达 
                if(indl[vv]==0&&vis[vv]==false)        
                    {dl1[tail1++]=vv;indl[vv]=1;}    //放到遍历的队列中去 
                else continue;
            else if(indl[vv]==0&&vis[vv]==false)      
                    {dl2[tail2++]=vv;indl[vv]=2;}    //如果不能到达，放到另外一个队列中去，待会再搜一次 
        }               //注意：在入队时只能取不在队列且未被访问过的房间，不然会导致重复搜索，甚至无限递归 
    }
    if(flag)        //如果有房间可以被到达 
    {
        for(int i=head2;i<=tail2;++i)
            dl1[i]=dl2[i];
        head1=head2;tail1=tail2;      //上三行主要是懒得写两个函数于是用队列2覆盖队列1 
        bfs();               //继续搜索 
    }
}
inline int read()   //日常读入优化 
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    memset(indl,0,sizeof(indl));
    memset(light_up,0,sizeof(light_up));
    memset(vis,0,sizeof(vis));
    n=read();m=read();
    to[0]=-1*n;to[1]=1;to[2]=n;to[3]=-1;
    while(m--)
    {
        sp=(((xx=read())-1)*n+(yy=read()));  //降维操作 
        ep=(((xx=read())-1)*n+(yy=read()));     //降维操作 
        ins(sp,ep);
    }
    dl1[tail1++]=1;indl[1]=1;
    vis[1]=true;light_up[1]=true;      //以上为各种初始化 
    bfs();
    printf("%d",ans);
    return 0;
}

来源：LDlornd 的博客