uva 10318

滿不錯的題目，暴力加剪枝

//============================================================================
// Name        : Security Panel.cpp
// Date : 2013/3/31 下午9:48:08
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
    printf("%d ",dp[htx][hty]);}Pln();}
#define M 55
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
    int tmp=min(x,y);
    return min(tmp,z);
}
int max3(int x,int y,int z){
    int tmp=max(x,y);
    return max(tmp,z);
}
int nx,ny;
int mz[10];
int path[10][10];
int ans[100];
int ansnum;
void light(int x,int y){
    for(int i=y-1;i<=y+1;i++){
        if(i>=ny||i<0)continue;
        for(int j=x-1;j<=x+1;j++){
            if(j>=nx||j<0)continue;
//            debug("%d %d\n",j-x+1,i-y+1);
            if(path[j-x+1][i-y+1]){
//                debug("i%d j%d\n",i,j);
                mz[i]^=(1<<j);
            }
        }
    }
}
bool dfs(int now,int depth){
//    debug("now%d %d\n",now,depth);
//    for(int i=0;i<ny;i++){
//        for(int j=0;j<nx;j++){
////            printf("%d ",(mz[i]>>j)&1);
//        }//Pln();
//    }//Pln();


    int x=now%nx;
    int y=now/nx;
    if(y>=2&&y<ny&&mz[y-2]!=(1<<(nx))-1){
        return false;
    }

    bool judge=true;
    for(int i=0;i<ny;i++){
        if(mz[i]!=(1<<nx)-1){
            judge=false;
            break;
        }
    }
    if(judge){
        return true;
    }
    if(now>nx*ny-1)return false;

    if(dfs(now+1,depth))return true;
    light(x,y);
    ansnum=depth;
    ans[depth]=now+1;
    if(dfs(now+1,depth+1))return true;
    light(x,y);

    return false;
}
int main() {
    ios_base::sync_with_stdio(0);
    int ff=0;
    while(~scanf("%d%d%*c",&ny,&nx)&&nx+ny){
        char c;
        Set(path,0);
        Set(ans,0);
        Set(mz,0);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                c=getchar();
                if(c=='*')path[j][i]=1;
            }getchar();
        }
//        for(int i=0;i<3;i++){
//            for(int j=0;j<3;j++){
//                printf("%d ",path[j][i]);
//            }Pln();
//        }Pln();
        printf("Case #%d\n",++ff);
        if(dfs(0,0)){
            printf("%d",ans[0]);
            for(int i=1;i<=ansnum;i++){
                printf(" %d",ans[i]);
            }Pln();
        }
        else printf("Impossible.\n");
    }


}