题解 P2845 【[USACO15DEC]Switching on the Lights S】

· · 题解

• 基本思路

很明显，这是一篇 BFS 的题，但 BFS 能解决的 DFS 也可以。

从 (1,1) 房间开始，上下左右搜，把当前房间能打开的灯都打开，然后继续搜。

但是我们来看一下下面这个样例：

3 4
1 1 1 2
1 2 2 1
2 1 1 3
1 3 3 1

我们可以模拟到，当 (2,1) 打开 (1,3) 之后，(2,1) 周围没有开着灯的房间，DFS 就结束了，我们没法再回到 (1,3) 打开 (3,1)，所以按照这个思路，最后会输出 4，但答案是 5。

1 1 1
1 0 0
X 0 0

很多 dalao 都表示应该往回搜，但本蒟蒻不是很懂其原理，实际上我们可以反复 DFS，期间 mark 不清零，然后将这一次的结果和上一次结果比较，如果相同就证明没有漏网之鱼，可以直接输出；不相同就更新为这一次结果，然后继续执行以上操作。

同样的样例，在第二次 DFS 搜到 (1,3) 的时候，就可以打开 (3,1)，同理，如果有 (4,1) 就进行第三次 DFS。

• 具体代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,x,y,a,b,ans,ans1;
//ans记录能打开灯的房间数量 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool mark[101][101],z[101][101];
//mark[i][j]表示(i,j)房间的电灯状态
//z[i][j]表示(i,j)房间是否走过 
struct l{
    int x[10001],y[10001],top;
}m[101][101];
//x[i]和y[i]分别表示当前房间第i个能控制的房间坐标
//top表示当前房间能控制的房间数量
void dfs(int x,int y){
    for(int i=1;i<=m[x][y].top;i++)
        mark[m[x][y].x[i]][m[x][y].y[i]]=1;
        //将当前房间能打开的都打开 
    for(int i=0;i<4;i++)
        if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=n&&mark[x+dx[i]][y+dy[i]]&&!z[x+dx[i]][y+dy[i]]){
            z[x+dx[i]][y+dy[i]]=1;
            dfs(x+dx[i],y+dy[i]);
        }
}
int main(){
    mark[1][1]=1,z[1][1]=1;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>x>>y>>a>>b;
        m[x][y].x[++m[x][y].top]=a,m[x][y].y[m[x][y].top]=b;
        //记录(x,y)房间能控制的房间坐标
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mark[i][j])ans++;
            //统计所有开着灯的房间数量 
    while(ans!=ans1){
        ans1=ans;//ans1存储上一次DFS的值 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                z[i][j]=0;
        dfs(1,1); 
        ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(mark[i][j])ans++;
                    //更新ans的值 
    }
    cout<<ans;
    return 0;
}