题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4012
下面分析转自大牛：http://www.cnblogs.com/ambition/archive/2011/09/08/Paint_on_a_Wall.html
题目大意：给出一个2×n的矩阵（n<=8），每次给一个矩形染色，之后的染色覆盖以前的颜色，问到达目标状态需要多少次
看到题目数据量想到了要用搜索去做，想了很久才想出搜索方法，搜索题中的极品啊～～
因为每一次涂色肯定会有至少一块颜色是最终显示的颜色，所以用状态记录每一块是否是最终显示的颜色，因为只有2×8块，用二进制表示，搜索的顺序是每一块被染色顺序，在对某一块染色时把这个块最大能扩展到矩形全部染色，并将其中颜色和那一块相同的全部标记为最终显示的颜色
扩展就是向前和向后分别去判断，如果要扩展的块已经是最终显示颜色了，那么就不能扩展下去了，这样找到染色当前块的最大矩形，每个块可以扩展成单行和双行两种矩形
下面的代码我自己添加了一些解释，不难看懂：
#include<iostream>
#include<queue>
using namespace std;
struct node
{
int v,cnt;
//v标记当前状态，即16点是否已经全部达到最终状态
//cnt表示当前状态已用的操作数
};
queue<node> Q;
char maze[20];//原矩阵
bool vis[1<<16];
int n;
int bfs()
{
node q;
q.v=q.cnt=0;
Q.push(q);
memset(vis,false,sizeof(vis));
vis[0]=true;
while(!Q.empty())
{
node tmp;
q=Q.front();
int u=q.v;
Q.pop();
for(int i=0;i<(n<<1);i++)
{
int v=u;
if(v&(1<<i)) //若当前节点已经达到最终状态，continue
continue;
for(int j=i;j<(i/n+1)*n;j++)//循环控制好精湛啊，当时使用于i处在第一行和第二行的情况，从当前点向右遍历，看是否下一点是否相同
{
if(v&(1<<j)) break;
if(maze[i]==maze[j]) v|=(1<<j);
}
for(int j=i-1;j>=(i/n)*n;j--)//从当前点向左遍历
{
if(v&(1<<j)) break;
if(maze[i]==maze[j]) v|=(1<<j);
}
if(!vis[v])
{
vis[v]=true;
if(v==(1<<(n<<1))-1)//当前状态，所有点都达到最终状态
return q.cnt+1;
tmp.v=v;
tmp.cnt=q.cnt+1;
Q.push(tmp);
}
if(i/n)//下面是对每次画一个二行的矩阵的情况进行的讨论，所以当i大于n是continue
continue;
v=u;
if(v&(1<<(i+n))) //若当前点的下方已经是最终状态，则无需画一个二行的矩阵，continue
continue;
for(int j=i;j<n;j++)//向右遍历
{
if((v&(1<<j))|(v&(1<<(j+n)))) //当前点或当前点的下面 的点已经到达最终状态
break;
if(maze[i]==maze[j]) v|=(1<<j);
if(maze[i]==maze[j+n]) v|=(1<<(j+n));
}
for(int j=i-1;j>=0;j--)//向左遍历
{
if((v&(1<<j))|(v&(1<<(j+n))))break;
if(maze[i]==maze[j]) v|=(1<<j);
if(maze[i]==maze[j+n]) v|=(1<<(j+n));
}
if(!vis[v])
{
vis[v]=true;
if(v==(1<<(n<<1))-1)
return q.cnt+1;
tmp.v=v;
tmp.cnt=q.cnt+1;
Q.push(tmp);
}
}
}
}
int main()
{
int cas,T=0;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
scanf("%s",maze);
scanf("%s",maze+n);
while(!Q.empty())
Q.pop();
printf("Case #%d: %d\n",++T,bfs());
}
return 0;
}