poj 1691 搜索

今天药忘吃喽~ 2021-11-02 14:24 260阅读 0赞

1.题意：

![2012073016050940.jpg][]

给你个一平板由N个矩阵组成，先Y后X，给出的点是矩阵左上角和右下角。

每个矩阵可以用一种颜色刷子粉刷，求把这平板按指定颜色全部涂色，并且该平板是竖的，当前粉刷的矩阵要保证其上面没有未粉刷的矩阵，求最少的换刷子次数？

算法：

1.根据规则建好图。

2.根据N比较少，可以用dp状态压缩或直接DFS回溯，我写的是回溯，还可以用记忆化搜索。

dp\[i\]\[j\]  = c 表示最后粉刷的是第i个矩阵，已经粉刷的矩阵状态为j, 换粉刷次数为c

3. DFS 回溯

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    #define MAXN 1000
    
    struct Mt
    {
      int tx,ty,bx,by,color;//左上角， 右下角 
      bool flag;       
    }M[MAXN];
    
    int N, T, mp[50][50], in[50];
    int maxn;
    
    void build_Graph( )
    {
      for( int i = 1; i <= N; i++)
      {
         for( int j = 1; j <= N; j++)
         {
            if( j == i )
                continue;
            if( M[i].by == M[j].ty )
            {
               if( !(M[j].bx < M[i].tx || M[j].tx > M[i].bx) )
               {
                  in[j]++;
                  mp[i][j] = 1;    
               }
                
            }     
              
         }     
           
      }
         
    }
    
    void color( int x )
    {
      for( int i = 1; i <= N; i++)
      {
         if( M[i].flag || in[i] || M[i].color != x )
             continue;
         M[i].flag = 1;
         for( int j = 1; j <= N; j++)
         {
            if( mp[i][j] )
                in[j]--;  
         }     
           
      }     
         
    }
    
    void DFS( int num )
    {
      int i;
      if( num > maxn )
          return;
      for(i = 1; i <= N; i++)
      {
        if( M[i].flag == 0 )
            break;     
      }     
      if( i == N + 1 )
      {
         if( num < maxn )    
             maxn = num;
         return;
      }
      int flag[30],temp[30][30],in1[30];
      for( int i = 1; i <= N; i++)
      {
         if( M[i].flag || in[i] )
            continue;
         for( int j = 1; j <= N; j++)
         {
             flag[j] = M[j].flag;
             in1[j] = in[j];
             for( int k = 1; k <= N; k++)
             {
                temp[j][k] = mp[j][k];     
             }
              
         }
         color( M[i].color ); 
         DFS( num + 1);
         for( int j = 1; j <= N; j++)
         {
            M[j].flag = flag[j];
            in[j] = in1[j];
            for( int k = 1; k <= N; k++)
            {
               mp[j][k] = temp[j][k];     
            }     
              
         }    
           
      }   
    }
    
    int main( )
    {
      scanf("%d",&T);
      while(T--)
      {
        scanf("%d",&N);
        memset(mp,0,sizeof(mp));
        memset(in,0,sizeof(in));
        for( int i = 1; i <= N; i++)
        {
            scanf("%d%d%d%d%d",&M[i].ty,&M[i].tx, &M[i].by,&M[i].bx, &M[i].color);
            M[i].flag = false; 
        } 
        build_Graph( );    
        /*
        for( int i = 1; i <= N; i++)
             printf("%d\n",in[i]);
        for( int i = 1; i <= N; i++)
        {
           for( int j = 1; j <= N; j++)
                printf("%d ",mp[i][j]);
           puts("");
        }
        */
        maxn = 0x7f7f7f7f;
        DFS( 0 );
        printf("%d\n",maxn);
      }      
      return 0;  
    }

4.记忆话搜索（从网上找的别人代码，自己没写了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct Ret
    {
        int x1,y1,x2,y2,c;
    }ret[20];
    #define INF 1000000000
    int n;
    int dp[15][1<<15]; //dp[i][j]表示最后一个扩展的矩形是i...已扩展的矩形状态是j需要的最少数目
    bool used[15];
    int res;
    bool up[20][20];
    void init()
    {
         memset(used,0,sizeof(used));
         res=INF;
         memset(up,0,sizeof(up));
         for(int i=0;i<n;i++)
         {
             for(int j=i+1;j<n;j++)
             if(ret[j].x1==ret[i].x2&&!(ret[i].y2<=ret[j].y1||ret[i].y1>=ret[j].y2))
             up[i][j]=true;
         }
         for(int i=0;i<n;i++)
         {
             for(int j=0;j<1<<n;j++)
             {
                 dp[i][j]=INF;
             }
         }
    }
    bool dfs(int k,int last,int count,int use)
    {
         if(k==n)
         {
             if(count<res)
             {
                 res=count;
                 return true;
             }
             return false;
         }
         if(last!=-1&&count>dp[last][use])
         {
           return false;
         }
         bool ok=false;
         int now=INF;
         if(count>res)
         return false;
         for(int i=0;i<n;i++)
         {
            if(!used[i])
            {
                bool judge=false;
                for(int j=0;j<n;j++)
                {
                    if(up[j][i]&&!used[j])
                    {
                        judge=true;
                        break;
                    }
                }
                if(judge)
                continue;
                bool temp=false;
                if(last==-1||ret[last].c!=ret[i].c)
                temp=true;
                used[i]=true;
                if(dfs(k+1,i,count+temp,use|1<<i))
                ok=true;
                used[i]=false;
            }
         }
         if(last!=-1&&!ok)
         dp[last][use]=count-1;
         else if(last!=-1&&ok)
         dp[last][use]=count;
    }
    int cmp(const Ret &a,const Ret &b)
    {
        if(a.x1!=b.x1)
        return a.x1<b.x1;
        else if(a.x2!=b.x2)
        return a.x2<b.x2;
        else if(a.y1!=b.y1)
        return a.y1<b.y1;
        else 
        return a.y2<b.y2;
    }
    int main()
    {
        int cases;
        scanf("%d",&cases);
        while(cases--)
        {
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            scanf("%d%d%d%d%d",&ret[i].x1,&ret[i].y1,&ret[i].x2,&ret[i].y2,&ret[i].c);
            sort(ret,ret+n,cmp);
            init();
            dfs(0,-1,0,0);
            printf("%d\n",res);
        }
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/30/2615445.html

[2012073016050940.jpg]: /images/20211101/0f27cb97659347af9bd36bf486c0900b.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/3de10d473eec41f4b6f88f0754f1d58b.png