首页 > 搜索 > BFS搜索 > HDU 4012-Paint on a Wall-BFS-[解题报告]HOJ
2015
04-15

HDU 4012-Paint on a Wall-BFS-[解题报告]HOJ

Paint on a Wall

问题描述 :

Annie wants to paint her wall to an expected pattern. The wall can be represented as a 2*n grid and each grid will be painted only one color. Annie has a brush which could paint a rectangular area of the wall at a single step. The paint could be overlap and the newly painted color will replace the older one.
  For a given pattern of the wall, your task is to help Annie find out the minimum possible number of painting steps. You can assume that the wall remains unpainted until Annie paint some colors on it.

输入:

There are multiple test cases in the input. The first line contains the number of test cases.
  For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)
  Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.
  See the sample input for further details.

输出:

There are multiple test cases in the input. The first line contains the number of test cases.
  For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)
  Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.
  See the sample input for further details.

样例输入:

3
3
ABA
CBC
3
BAA
CCB
3
BBB
BAB

样例输出:

Case #1: 3
Case #2: 3
Case #3: 2

题目链接~~>

做题感悟:这题只能说很“ 经典 ” 。

解题思路:题意就是给你一个二行N例的一面墙,在墙上涂颜色,问你最少粉刷多少次,能达到给你的目标墙的状态,(每次粉刷只能粉刷出一个矩形,矩形可以是一行N例,也可以是二行N例);

思想:广度优先搜索(因为找最短路)

状态表示:
状态用二制位表示。例如当N=4时,就用8位二进制数表示状态如:
   1100
1010
‘‘0’’表示与目标状态颜色不一致,‘1’表示一致。
初始状态当然为:
0000
0000
因为和目标状态没有相同颜色。
目标状态自然为:
1111
1111
状态转移:
状态转移就是粉刷墙的过程,按传统套路很容易把粉刷的颜色也考虑进去。这样就走弯路了。
仔细想想会发现 每次粉刷,都会使一状态中的一些0变成1。从而越来越接近目标状态。
问题来了,每次粉刷多大?粉刷的大小受什么影响?
先分两种情况:
第一种是刷一行,在图上选一个点的颜色粉刷,分别向该点的左右粉刷,如果遇到和选取点颜色相同,则将当前状态该位的0变成1,表示与目标状态相同
第二种是刷两行,刷两行只考虑一行就可以,在其中一行寻解时,同时考虑同列的另一行,也就是在列相同的情况下判断两行的颜色,以及粉刷。
这样就可以从一个状态转移到另一个状态。
注:上述方法可以得到一个极大粉刷区域,每次状态转移全是转移最大粉刷区域,显然是不够准确的,算出最大粉刷区域后应该也将该区域的子集加到扩展队列中。求一个状态的子集的方法:整数temp的位数为当前状态 ,那么for(int j=temp;j;j=temp&(j-1));j就为子状态。可以自己模拟体会一下。
判重:
根据状态抽象,最多有2<16种状态,可以开一个bool型数组flag[1<<16];如flag[i]=1,则表示i二进制位表示的这个状态以经出现过。
代码:
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN   sizeof(struct node)
#define pret(a,b) memset(a,b,sizeof(a))
#define lld __int64
const double PI = 3.1415926 ;
const double INF = 999999999 ;
const double esp = 1e-4 ;
const lld  md= 2810778 ;
const int MX = 20 ;
int n ;
char s[MX] ;
bool vis[1<<16] ;
struct node
{
    int key,step ; // key 表状态 step 记录步数
} ;
int bfs()
{
    queue<node>q ;
    node curt,next ;
    while(!q.empty()) q.pop() ;
    memset(vis,false,sizeof(vis)) ;
    curt.key=curt.step=0 ;
    vis[0]=true ;
    q.push(curt) ;
    while(!q.empty())
    {
        curt=q.front() ;
        q.pop() ;
        for(int i=0 ;i<(n<<1) ;i++) // 遍历每一个点
        {
            int key=curt.key,ky=0 ;
            next.step=curt.step+1 ; // 步数加一
            if(key&(1<<i))      continue ;
            //   先单行左右扩展
            for(int j=i ;j<(i/n+1)*n ;j++)// 从当前节点向右扩展
            {
                if(key&(1<<j)) break ;// 遇到已经染色的就结束
                if(s[i]==s[j]) ky=ky|(1<<j) ; // 与起始颜色一样 ~> 染色
            }
            for(int j=i-1 ;j>=(i/n)*n ;j--) // 从当前节点向左扩展
            {
                if(key&(1<<j)) break ;
                if(s[i]==s[j]) ky=ky|(1<<j) ;
            }
            if((key|ky)==(1<<(n*2))-1) return next.step ; // 放在这可以减少时间
            for(int j=ky ;j ;j=key&(j-1))
            {
               if(!vis[key|j])
               {
                   vis[key|j]=true ;
                   next.key=key|j ;
                   q.push(next) ;
               }
            }
            // 以上为单行双向扩展
            if(i/n)  continue ;
            key=curt.key ; ky=0 ;
            if(key&(1<<(i+n))) continue ;
            for(int j=i ;j<n ;j++)
            {
                if((key&(1<<j))||(key&(1<<(j+n)))) break ;
                if(s[i]==s[j]) ky=ky|(1<<j) ;
                if(s[i]==s[j+n])ky=ky|(1<<(j+n)) ;
            }
            for(int j=i-1 ;j>=0 ;j--)
            {
                if((key&(1<<j))||(key&(1<<(j+n)))) break ;
                if(s[i]==s[j])  ky=ky|(1<<j) ;
                if(s[i]==s[j+n]) ky=ky|(1<<(j+n)) ;
            }
            if((key|ky)==(1<<(n*2))-1) return next.step ; 
            for(int j=ky ;j ;j=ky&(j-1)) // 切记要枚举子集:因为并不一定需要涂最大区域,如果涂了最大区域
            {                           //别的地方就没法连续涂了。
                if(!vis[key|j])
                {
                    vis[key|j]=true ;
                    next.key=key|j ;
                    q.push(next) ;
                }
            }
        }
    }
    return 0 ;
}
int main()
{
    int Tx,q=1 ;
    scanf("%d",&Tx) ;
    while(Tx--)
    {
        scanf("%d",&n) ;
        scanf("%s",s) ; // 用一维存储
        scanf("%s",s+n) ;
        printf("Case #%d: %d\n",q++,bfs()) ;
    }
    return 0 ;
}

 

参考:http://blog.csdn.net/nyist_zxp/article/details/23338569