Acwing2013. three lines

sample input ：

6
1 7
0 0
1 2
2 0
1 4
3 4

sample output ：

1

Sample explanation

y=0,x=1,y=4 It can cover the positions of all cows .

Answer key （DFS）

1. First select a point , He has two options , use x perhaps y Line of direction ,

2. After selecting the direction , Delete all points in this direction

3. Then randomly select one of the undeleted points , Repartition x or y Direction , Repeat the first 2 Step

4. Then repeat step three

5. After the first four steps , The deleted points are crossed by three lines , At this point, the result can be obtained by judging whether there is any left

6. If there are still points left, it means that this scheme is not tenable , Then you can backtrack and rotate in different directions

7. So there are 8 Select the direction combination of lines , Here's the picture

Code thinking ：

• use dfs Recursive three-tier implementation

• Use one Struct To determine whether coordinates and record points are deleted

• Use an array to record all points

• To prevent traversing the array every time, judge whether the point is deleted , The starting point of each layer traversal is the new line decision point , All the previous points have been deleted （ That is, it has been wired through ）, The point after the start point contains both deleted and undeleted points in the array

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 50010;

struct Node{
    
        int x,y,status;
}node[N];

int n;

int dfs(int index, int level){
    
        if(level == 0){
    
                if(index != n) return 0;
                else return 1;
        }
        int next = n;
        node[index].status = 1;
        // try x line
        for(int i = index+1;i<n;i++){
    
                if(node[i].x == node[index].x){
    
                        node[i].status = 1;
                }else if(node[i].status){
    
                        continue;
                }else{
    
                        next = i;
                        break;
                }
        }
        for(int i = next+1;i<n;i++){
    
                if(node[i].x == node[index].x){
    
                        node[i].status = 1;
                }else if(node[i].status){
    
                        continue;
                }
        }
        int ret = dfs(next,level-1);
        for(int i = index+1;i<n;i++){
      //  to flash back 
                if(node[i].x == node[index].x){
    
                        node[i].status = 0;
                }
        }
        
        // try y line
        next = n;
        for(int i = index+1;i<n;i++){
    
                if(node[i].y == node[index].y){
    
                        node[i].status = 1;
                }else if(node[i].status){
    
                        continue;
                }else{
    
                        next = i;
                        break;
                }
        }
        for(int i = next+1;i<n;i++){
    
                if(node[i].y == node[index].y){
    
                        node[i].status = 1;
                }else if(node[i].status){
    
                        continue;
                }
        }
        ret = dfs(next,level-1) or ret;
        for(int i = index;i<n;i++){
      //  to flash back 
                if(node[i].y == node[index].y){
    
                        node[i].status = 0;
                }
        }
        return ret;
}

int main(){
    
        cin>>n;
        for(int i = 0;i<n;i++){
    
                cin>>node[i].x>>node[i].y;
                node[i].status = 0;
        }
        
        cout<<dfs(0,3)<<endl;
        
        return 0;
}