POJ 1691 Painting A Board(迭代深搜)

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 using namespace std;
  5 struct node
  6 {
  7     int x1,y1,x2,y2,c;
  8 } p[21];
  9 struct n1
 10 {
 11     int u,v,next;
 12 } edge1[2000],edge2[2000];
 13 int first1[21],first2[21];
 14 int to1,to2,n;
 15 int o[21];
 16 void CL()
 17 {
 18     to1 = to2 = 0;
 19     memset(first1,-1,sizeof(first1));
 20     memset(first2,-1,sizeof(first2));
 21 }
 22 int fun(int x,int y)
 23 {
 24     if(p[x].x2 <= p[y].x1)
 25     {
 26         if(p[x].y1 < p[y].y2&&p[x].y1 > p[y].y1)
 27             return 1;
 28         else if(p[x].y2 < p[y].y2&&p[x].y2 > p[y].y1)
 29             return 1;
 30         else if(p[y].y1 < p[x].y2&&p[y].y1 > p[x].y1)
 31             return 1;
 32         else if(p[y].y2 < p[x].y2&&p[y].y2 > p[x].y1)
 33             return 1;
 34         else if(p[x].y1 == p[y].y1&&p[x].y2 == p[y].y2)
 35             return 1;
 36         else
 37             return 0;
 38     }
 39     return 0;
 40 }
 41 void add1(int u,int v)
 42 {
 43     edge1[to1].u = u;
 44     edge1[to1].v = v;
 45     edge1[to1].next = first1[u];
 46     first1[u] = to1 ++;
 47 }
 48 void add2(int u,int v)
 49 {
 50     edge2[to2].u = u;
 51     edge2[to2].v = v;
 52     edge2[to2].next = first2[u];
 53     first2[u] = to2 ++;
 54 }
 55 int judge(int x)
 56 {
 57     int i;
 58     for(i = first2[x];i != -1;i = edge2[i].next)
 59     {
 60         if(!o[edge2[i].v])
 61         break;
 62     }
 63     if(i == -1)
 64     return 1;
 65     else
 66     return 0;
 67 }
 68 int dfs(int x,int c,int step)
 69 {
 70     int i;
 71     if(x < 0)
 72     return 0;
 73     if(step > n)
 74     return 1;
 75     for(i = 1;i <= n;i ++)
 76     {
 77         int z = judge(i);
 78         if(!o[i]&&z&&c == p[i].c)
 79         {
 80             o[i] = 1;
 81             if(dfs(x,p[i].c,step+1))
 82             {
 83                 return 1;
 84             }
 85             o[i] = 0;
 86         }
 87         else if(!o[i]&&z&&c != p[i].c)
 88         {
 89             o[i] = 1;
 90             if(dfs(x-1,p[i].c,step+1))
 91             {
 92                 return 1;
 93             }
 94             o[i] = 0;
 95         }
 96     }
 97     return 0;
 98 }
 99 int main()
100 {
101     int t,i,j;
102     scanf("%d",&t);
103     while(t--)
104     {
105         scanf("%d",&n);
106         CL();
107         for(i = 1; i <= n; i ++)
108         {
109             scanf("%d%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2,&p[i].c);
110         }
111         for(i = 1; i <= n; i ++)
112         {
113             for(j = 1; j <= n; j ++)
114             {
115                 if(i != j)
116                 {
117                     if(fun(i,j))
118                     {
119                         add1(i,j);
120                         add2(j,i);
121                         //printf("%d %d
",j,i);
122                     }
123                 }
124             }
125         }
126         for(i = 1;i <= n-1;i ++)
127         {
128             memset(o,0,sizeof(o));
129             if(dfs(i,0,1))
130             break;
131         }
132         printf("%d
",i);
133     }
134     return 0;
135 }