补题：HOJ暑期训练第五场：Illumination（hoj-14156） (2-sat问题）

女爷i 2022-05-16 10:12 157阅读 0赞

题目链接：  
[Illumination][]

题目大意：  
在一个n\*n的网格中，给你l盏灯，灯可以横着照亮2r+1长的范围，也可以竖着照，但是要求网格上的所有交点都需要满足不能同时被同一行或者同一列两个灯照到（如果一个灯来自列，另一个灯来自行，是允许的）。现在给出灯的坐标，问你可否找到一种方案，使得满足上述要求

解题思路：  
我们可以把灯横着放和竖着放当作两种状态，假设横着放为1，竖着放为0，则可以发现当某盏灯为1或0时，如果要满足题目要求，可能另外某盏灯就需要为1； 那么抽象出来就是一个2-sat问题了。  
啥？？？ 不知道什么是2-sat问题。没事，为你准备了学习门，觉得不错的几篇介绍：  
[【研究总结】2-sat问题][2-sat]  
[2-sat分析+代码][2-sat 1]

好了，大概已经懂了吧！！！  
于是，我们需要把在同一行或者同一列，且他们之间距离小于等于r的灯根据他们的关系建边。  
建好边，套一下2-sat问题模板（即从一个未标记点先假设为真出发，如果dfs中遇到矛盾点，则false，继续假设该点为假，也行不通的话，该2-sat问题无解）就好。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    struct point{
        int x, y;
    }p[2500];
    
    vector<int> g[2500];
    
    int n,r,l,c;
    int S[2500],mark[2500];
    
    bool dfs(int x){
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x] = 1;
        S[c++] = x;
        for(int i=0; i<g[x].size(); ++i){
            if(!dfs(g[x][i])) return false;
        }
        return true;
    }
    
    bool solve(){
        for(int i=0; i<2*l; i+=2){
            if(!mark[i]&&!mark[i^1]){
                c = 0;
                if(!dfs(i)){
                    while(c>0) mark[S[--c]] = 0;
                    if(!dfs(i^1)) return false;
                }
            }
        }
        return true;
    }
    
    void init(){
        for(int i=0; i<2*l; ++i) g[i].clear();
        memset(mark, 0, sizeof(mark));
        memset(S, 0, sizeof(S));
    }
    
    int main(int argc, char const *argv[])
    {
        init();
        cin>>n>>r>>l;
        for(int i=0; i<l*2; i+=2){
            cin>>p[i].x>>p[i].y;
            for(int j=0; j<i; j+=2){
                if(p[i].x == p[j].x && abs(p[i].y-p[j].y) <=r){
                    g[i].push_back(j^1);
                    g[j].push_back(i^1);
                }
                if(p[i].y == p[j].y && abs(p[i].x-p[j].x) <=r){
                    g[i^1].push_back(j);
                    g[j^1].push_back(i);
                }
            }
        }
    
        if(solve()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        return 0;
    }

[Illumination]: http://acm.hnu.cn/online/?action=problem&type=show&id=14156
[2-sat]: https://blog.csdn.net/jarjingx/article/details/8521690
[2-sat 1]: https://blog.csdn.net/wu_tongtong/article/details/78008148