2949.cpp

poj题目2949平板着色问题

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int RectAbove[15];
int used[65540];
struct Rect{
            int X1,Y1,X2,Y2;
            int c;
            }rect[15];
int rectID[16];
int n; 
int object; 
bool above(int x,int y)
{
      if (rect[y].Y2==rect[x].Y1)
       {
        if (rect[y].X1<rect[x].X2 && rect[y].X2>rect[x].X1)
        return true;
        } 
        return false;
}
int paint(int status) 
{
          int i, j, minPickups, pained, newStatus, pickups, color;
		  bool brushUsed;
          if (status == object ) 
			  return 0;
		  if(used[status]!=0)
			  return used[status];
           minPickups = 15;
           for(i=0; i<n; i++) 
		   {
           if ( status&rectID[i] ) continue; 
           if ( (status&RectAbove[i]) != RectAbove[i] ) continue; 
           color = rect[i].c;
           newStatus = status + rectID[i];
		   brushUsed=true;
		   while(brushUsed)
		   {
			   brushUsed=false;
              for ( j=0; j<n; j++ ) 
			  {
                 if ( rect[j].c != color ) continue;
                 if (newStatus&rectID[j] ) continue;
                 if ( (newStatus&RectAbove[j]) != RectAbove[j] ) continue;
                 newStatus = newStatus + rectID[j];
				 brushUsed=true;
              }
		   }
		     pickups = paint(newStatus) + 1;

            if ( pickups < minPickups ) 
				minPickups = pickups;
		   }
        
         used[status]=minPickups;
           return(minPickups);
}
int main()
{
        int T, i, j, status, minPickups;
          rectID[0]=1;
        for (i=1; i<16; i++) rectID[i]=rectID[i-1]<<1;
           scanf("%d",&T);
        for (;T>=1;T--)
		{
			memset(used,0,sizeof(used));
             scanf("%d",&n); 
             for (i=0;i<n;i++)
             {
               scanf("%d %d %d %d %d",&rect[i].Y1,&rect[i].X1,&rect[i].Y2,&rect[i].X2,&rect[i].c);
             }
           for (i=0;i<n;i++) 
		   {
             RectAbove[i]=0;
             for (j=0;j<n;j++)
              if (above(j,i))
             RectAbove[i]+=rectID[j];
           }
         status = 0;
         object = rectID[n] - 1;
         minPickups = paint(status);
         printf("%d\n",minPickups);
		}
           return 0;
}