AC题解

#include <bits/stdc++.h>
using namespace std;
int n;
int a[107],b[107],cur[107],change[107];
 
int cal(int num){
    int ans = 0;
    while(num){
        ans++;
        num &= num-1;
    }
    return ans;
}
 
int sol(int a[]){
    int ans = ~(1<<31);
    for(change[0] = 0;change[0]<(1<<n);change[0]++){
        int sum = 0;
        cur[0] = a[0];
        for(int i = 0;i<n;i++){
            sum += cal(change[i]);
            cur[i] = cur[i] ^ change[i] ^ (change[i]>>1) ^ ((change[i]<<1)&((1<<n)-1));
            cur[i+1] = a[i+1] ^ change[i];
            change[i+1] = cur[i];
        }
        if(!cur[n-1]) ans = min(ans,sum);
    }
    return ans;
}
 
 
int main(){
    std::ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            char tmp;
            cin>>tmp;
            if(tmp == 'b') a[i] |= (1<<j);
            else if(tmp == 'w') b[i] |= (1<<j);
        }
    }
    int ans = min(sol(a),sol(b));
    if(ans>n*n) cout<<"Impossible"<<'\n';
    else cout<<ans<<'\n';
    return 0;
}