首先来看这样一道题：
Gym 101201F Illumination (Two-Sat)
题目链接
题意：一个n*n的房子，有很多灯，每个格子只能被上下方向照一次、左右方向照一次，每个灯可以选择上下或是左右照，照明长度以自身位置为中心，占用2*r+1个格子。问能否安排一种方案，使所有格子满足条件。
析：典型的Two-Sat，对于行来说，如果两个能够交叉，那么他们不能都是左右，对于列也是一样。
参考博客：这里写链接内容
算法学习博客：
学习1
各种模型
hzw缩点法
学习2
AC代码：tarjan缩点版

自己仿写的模板

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4+7;
typedef pair<int,int> P;
struct TWOSAT
{
     int n;
     vector<int>G[maxn];
     bool mark[maxn];
     int S[maxn],c;
     bool dfs(int x)
     {
         if(mark[x^1])return 0;
         if(mark[x])return 1;
         mark[x] = 1;
         S[c++] = x;
         for(int i=0;i<(int )G[x].size();i++)
            if(!dfs(G[x][i]))return 0;
        return 1;
     }
     void add_claues(int x,int xval,int y,int yval)
     {
         x = x*2+xval;
         y = y*2+yval;
         G[x^1].push_back(y);
         G[y^1].push_back(x);
     }
     bool solve()
     {
         for(int i=0;i<n*2;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 0;
                 }
             }
         }
         return 1;
     }
};
map<P,int>mp;
vector<int>row[1005],col[1005];
TWOSAT exsat;
int main()
{
    int n,r,l;
    cin>>n>>r>>l;
    int cnt = 0;
    for(int i=0;i<l;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        mp[make_pair(x,y)] = cnt++;
        row[x].push_back(y);
        col[y].push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        sort(row[i].begin(),row[i].end());
        sort(col[i].begin(),col[i].end());
    }
    exsat.n = cnt;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(int)row[i].size();j++)
        {
            int k = j+1;
            while(k<(int)row[i].size()&&row[i][j]+r>=row[i][k])
            {
                exsat.add_claues(mp[P(i,row[i][j])],1,mp[P(i,row[i][k])],1);
                k++;
            }
        }
        for(int j=0;j<(int)col[i].size();j++)
        {
            int k = j+1;
            while(k<(int)col[i].size()&&col[i][j]+r>=col[i][k])
            {
                exsat.add_claues(mp[P(col[i][j],i)],0,mp[P(col[i][k],i)],0);
                k++;
            }

        }
    }
    if(exsat.solve())printf("YES\n");
    else printf("NO\n");
    return 0;
}

样例：
Sample Input
3 2 5
1 1
1 3
3 1
3 3
2 2
Sample Output
YES
Sample Input
3 2 6
1 1
1 2
1 3
3 1
3 2
3 3
Sample Output
NO
ps：事实上这道题目的数据非常水
如下的dfs也可过：（只判断灯）

#include<bits/stdc++.h>
using namespace std;
int mp[1007][1007]={0};
int ans;
int aa[1008];
int bb[1008];
int vv[1007][1007];
int n,r,l;
void dfs(int x,int y,int flag)
{
    vv[x][y] = flag;
    int tx,ty;
    for(int i=-r;i<=r;i++)
    {
        if(i==0)continue;
        if(!flag) tx = x,ty = i+y;
        else tx = i+x,ty = y;
        if(tx<1||tx>n||ty<1||ty>n)continue;
        if(!mp[tx][ty])continue;
        if(vv[tx][ty]==-1)
        {
            //vv[tx][ty] = flag^1;
            dfs(tx,ty,flag^1);
            if(ans==1)
            {
                vv[tx][ty] =-1;
                return;
            }
        }
        else if(vv[tx][ty]==flag)
        {
            ans = 1;
            return;
        }
    }
}
int main()
{

    memset(vv,-1,sizeof vv);
    cin>>n>>r>>l;
    int x,y;
    for(int i=1;i<=l;i++)
    {
        cin>>x>>y;
        mp[x][y] = 1;
        aa[i] = x;
        bb[i] = y;
    }
    int i;
    for(i=1;i<=l;i++)
    {
        if(vv[aa[i]][bb[i]])
        {
             ans =0;
        dfs(aa[i],bb[i],0);
        if(ans==1)
        {
            ans =0 ;
            dfs(aa[i],bb[i],1); if(ans)break;
        }

        }

    }
    if(i<=l)printf("NO\n");
    else printf("YES\n");
    return 0;
}