做题感悟：这题只能说很“ 经典 ” 。
解题思路：题意就是给你一个二行Ｎ例的一面墙，在墙上涂颜色，问你最少粉刷多少次，能达到给你的目标墙的状态，（每次粉刷只能粉刷出一个矩形，矩形可以是一行Ｎ例，也可以是二行Ｎ例）；
思想：广度优先搜索（因为找最短路）
状态表示：
状态用二制位表示。例如当Ｎ＝４时，就用8位二进制数表示状态如：
1100
1010
‘‘０’’表示与目标状态颜色不一致，‘１’表示一致。
初始状态当然为：
0000
0000
因为和目标状态没有相同颜色。
目标状态自然为：
1111
1111
状态转移：
状态转移就是粉刷墙的过程，按传统套路很容易把粉刷的颜色也考虑进去。这样就走弯路了。
仔细想想会发现 每次粉刷，都会使一状态中的一些０变成１。从而越来越接近目标状态。
问题来了，每次粉刷多大？粉刷的大小受什么影响？
先分两种情况：
第一种是刷一行，在图上选一个点的颜色粉刷，分别向该点的左右粉刷，如果遇到和选取点颜色相同，则将当前状态该位的０变成１，表示与目标状态相同。
第二种是刷两行，刷两行只考虑一行就可以，在其中一行寻解时，同时考虑同列的另一行，也就是在列相同的情况下判断两行的颜色，以及粉刷。
这样就可以从一个状态转移到另一个状态。
注：上述方法可以得到一个极大粉刷区域，每次状态转移全是转移最大粉刷区域，显然是不够准确的，算出最大粉刷区域后应该也将该区域的子集加到扩展队列中。求一个状态的子集的方法：整数temp的位数为当前状态 ，那么for(int j=temp;j;j=temp&(j-1))；j就为子状态。可以自己模拟体会一下。
判重：
根据状态抽象，最多有２<１６种状态，可以开一个bool型数组flag[1<<16]；如flag[i]＝１,则表示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 ;
}