题目大意：求将一个r*c的按钮矩阵由全部为关变成全部为开的最少按扭次数，每按一次开关能作用到的范围不定。
题目分析：开关问题。打眼一看就是BFS+位压缩，但是写出来之后TLE。用DFS不断更新最优解。最坏有2^25种情况，加两个剪枝：
一、每一个开关最多只能影响三行，当第now_r-2行仍然有开关关着，则这种方案不可能使所有按钮全部打开，剪掉（并且是主剪）；
二、当当前总的按按钮次数大于已经达到的答案，则剪掉；
第二个剪枝效果不强，加不加都是26ms过，但不加第一个剪枝一定TLE。
这道题用BFS的话，上面两个剪枝起不到作用。
代码如下：
# include<iostream>
# include<cstdio>
# include<queue>
# include<map>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
struct XY
{
int x,y;
XY(int _x,int _y):x(_x),y(_y){}
};
char pos[3][3];
int cnt,r,c,mark[26];
bool flag;
vector<XY>d;
map<int,char>mp;
string ans;
void init()
{
d.clear();
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
if(pos[i][j]=='*')
d.push_back(XY(i-1,j-1));
}
}
}
bool ok()
{
for(int i=1;i<=r*c;++i)
if(mark[i]%2==0)
return false;
return true;
}
bool still_unlit(int row)
{
for(int i=(row-1)*c+1;i<=row*c;++i)
if(mark[i]%2==0)
return true;
return false;
}
int get_row(int n)
{
return (n%c)?(n/c)+1:(n/c);
}
void dfs(int id,string have)
{
if(ok()){
if(!flag){
flag=true;
ans=have;
}
else{
if(ans.size()>have.size())
ans=have;
}
return ;
}
if(id>c*2&&still_unlit(get_row(id-c*2)))
return ;
if(flag&&have.size()>ans.size())
return ;
for(int i=id+1;i<=r*c;++i){
int x=get_row(i),y=(i%c)?(i%c):c;
for(int j=0;j<d.size();++j){
int nx=x+d[j].x,ny=y+d[j].y,nid=(nx-1)*c+ny;
if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&nid>=1&&nid<=r*c)
++mark[nid];
}
dfs(i,have+mp[i]);
for(int j=0;j<d.size();++j){
int nx=x+d[j].x,ny=y+d[j].y,nid=(nx-1)*c+ny;
if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&nid>=1&&nid<=r*c)
--mark[nid];
}
}
}
int main()
{
for(int i=1;i<=26;++i)
mp[i]=i+'A'-1;
int cas=0;
while(scanf("%d%d",&r,&c)&&r+c)
{
for(int i=0;i<3;++i)
scanf("%s",pos[i]);
printf("Case #%d\n",++cas);
init();
memset(mark,0,sizeof(mark));
flag=false;
dfs(0,"");
if(flag){
for(int i=0;i<ans.size();++i)
printf("%d%c",ans[i]-'A'+1,(i==ans.size()-1)?'\n':' ');
}else
printf("Impossible.\n");
}
return 0;
}