poj-1753

#include <cstring>
#include <queue>
using namespace std;
const int kMaxN = 1 << 16;
bool kVis[kMaxN];
char kBoard[5][5];
struct {
    int step;
    int val;
    Location(int s, int v) : step(s), val(v){}
    Location(char b[5][5]){
        step = 0;
        val = 0;
        int mul = 1;
        for(int i = 3; i >= 0; --i){
            for(int j = 3; j >= 0; --j){
                if(b[i][j] == 'b'){
                    val += mul;
                }
                mul *= 2;
            }
        }
        step = 0;
    }
};
const int kBitOp[16] = {
    51200, 58368, 29184, 12544,
    35968, 20032, 10016, 4880,
    2248, 1252, 626, 305,
    140, 78, 39, 19
};
void Solve(){
    Location loc(kBoard);
    memset(kVis, false, sizeof(kVis));
    kVis[loc.val] = true;
    queue<Location> que;
    que.push(loc);
    while(!que.empty()){
        Location top = que.front();
        if(top.val == 0 || top.val == (kMaxN-1)){
            printf("%dn",top.step);
            return ;
        }
        que.pop();
        for(int i = 0; i < 16; ++i){
            Location next(top.step+1, top.val^kBitOp[i]);
            if(!kVis[next.val]){
                kVis[next.val] = true;
                que.push(next);
            }
        }
    }
    printf("Impossiblen");
}
int main(){
    while(scanf("%s",kBoard[0])!=EOF){
        for(int i = 1; i < 4; ++i){
            scanf("%s", kBoard[i]);
        }
        Solve();
    }
    return 0;
}