$DFS$
我们可以按每个点来搜索,然后控制线条个数$<3$这样我们递归的层数不会很多
然后开两个哈希表,记录放置的线
对于一个点$(x,y)$,若$sx.count(x)||sy.count(y)$说明我们不用新开一条线:$dfs(u+1,cnt)$
否则枚举放置水平还是竖直线:$dfs(u+1,cnt+1)$
记得回溯
Code:
时间复杂度:$O(8*n)$
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=5e4+10;
PII cow[N];
int n;
unordered_set<int>sx,sy;
bool dfs(int u,int cnt)
{
if(cnt>3)return false;
if(u==n){
return true;
}
int x=cow[u].first,y=cow[u].second;
if(sx.count(x)||sy.count(y))return dfs(u+1,cnt);
sx.insert(x);
if(dfs(u+1,cnt+1))return true;
sx.erase(x);
sy.insert(y);
if(dfs(u+1,cnt+1))return true;
sy.erase(y);
return false;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
scanf("%d%d",&cow[i].first,&cow[i].second);
}
cout<<dfs(0,0);
return 0;
}