[cpp] #include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=105;
int equ,var;
int a[N][N];
int b[N][N];
int x[N];
bool free_x[N];
int free_num;
int ans=100000000;
int absx(int x)
{
return x<0? -x:x;
}
void Debug()
{
int i,j;
for(i=0;i<equ;i++)
{
for(j=0;j<var+1;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int dfs(int p)
{
int i,j;
if(p<free_num)
{
for(i=free_num-1;i>=0;i--)
{
int temp=a[i][var]%2;
for(j=i+1;j<var;j++)
if(a[i][j]!=0)
temp=(temp-(a[i][j]*x[j])%2+2)%2;
x[i]=(temp/a[i][i])%2;
}
int sum=0;
for(int i=0;i<var;i++) sum+=x[i];
if(ans>sum) ans=sum;
return 0;
}
x[p]=0;
dfs(p-1);
x[p]=1;
dfs(p-1);
}
int Gauss()
{
int i,j,k,col=0;
for(k=0;k<equ&&col<var;k++,col++)
{
int max_r=k;
for(i=k+1;i<equ;i++)
{
if(a[i][col]>a[max_r][col]) max_r=i;
}
if(max_r!=k)
{
for(i=k;i<var+1;i++)
swap(a[k][i],a[max_r][i]);
}
if(a[k][col]==0)
{
k--;continue;
}
for(i=k+1;i<equ;i++)
{
if(a[i][col]!=0)
{
int LCM=lcm(a[i][col],a[k][col]);
int ta=LCM/a[i][col];
int tb=LCM/a[k][col];
if(a[i][col]*a[k][col]<0) tb=-tb;
for(j=col;j<var+1;j++)
a[i][j]=((a[i][j]*ta)%2-(a[k][j]*tb)%2+2)%2;
}
}
}
for(i=k;i<equ;i++)
if(a[i][col]!=0) return -1;
for(i=0;i<equ;i++)
{
if(!a[i][i])
{
for(j=i+1;j<var;j++)
if(a[i][j]) break;
if(j==var) break;
for(k=0;k<equ;k++)
swap(a[k][i],a[k][j]);
}
}
free_num=k;
if(var-k>0)
{
dfs(var-1);
return ans;
}
if(var-k==0)
{
for(i=k-1;i>=0;i--)
{
int temp=a[i][var]%2;
for(j=i+1;j<var;j++)
if(a[i][j]!=0)
temp=(temp-(a[i][j]*x[j])%2+2)%2;
x[i]=(temp/a[i][i])%2;
}
int sum=0;
for(i=0;i<var;i++) sum+=x[i];
return sum;
}
}
int main()
{
int i,j,k;
char str[20];
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
ans=1000000000;
for(i=0;i<4;i++)
{
cin>>str;
for(j=0;j<4;j++)
{
k=4*i+j;
a[k][k]=1;
if(i>0) a[k][k-4]=1;
if(i<3) a[k][k+4]=1;
if(j>0) a[k][k-1]=1;
if(j<3) a[k][k+1]=1;
if(str[j]=='b') a[k][16]=1;
}
}
for(i=0;i<16;i++)
for(j=0;j<=16;j++)
b[i][j]=a[i][j];
for(k=0;k<16;k++)
b[k][16]^=1;
equ=var=16;
int f1=Gauss();
int min1=ans;
for(i=0;i<16;i++)
for(j=0;j<=16;j++)
a[i][j]=b[i][j];
ans=100000000;
int f2=Gauss();
int min2=ans;
if (f1==-1&&f2==-1) cout<<"Impossible"<<endl;
else cout<<min(ans,min1)<<endl;
return 0;
}
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=105;
int equ,var;
int a[N][N];
int b[N][N];
int x[N];
bool free_x[N];
int free_num;
int ans=100000000;
int absx(int x)
{
return x<0? -x:x;
}
void Debug()
{
int i,j;
for(i=0;i<equ;i++)
{
for(j=0;j<var+1;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int dfs(int p)
{
int i,j;
if(p<free_num)
{
for(i=free_num-1;i>=0;i--)
{
int temp=a[i][var]%2;
for(j=i+1;j<var;j++)
if(a[i][j]!=0)
temp=(temp-(a[i][j]*x[j])%2+2)%2;
x[i]=(temp/a[i][i])%2;
}
int sum=0;
for(int i=0;i<var;i++) sum+=x[i];
if(ans>sum) ans=sum;
return 0;
}
x[p]=0;
dfs(p-1);
x[p]=1;
dfs(p-1);
}
int Gauss()
{
int i,j,k,col=0;
for(k=0;k<equ&&col<var;k++,col++)
{
int max_r=k;
for(i=k+1;i<equ;i++)
{
if(a[i][col]>a[max_r][col]) max_r=i;
}
if(max_r!=k)
{
for(i=k;i<var+1;i++)
swap(a[k][i],a[max_r][i]);
}
if(a[k][col]==0)
{
k--;continue;
}
for(i=k+1;i<equ;i++)
{
if(a[i][col]!=0)
{
int LCM=lcm(a[i][col],a[k][col]);
int ta=LCM/a[i][col];
int tb=LCM/a[k][col];
if(a[i][col]*a[k][col]<0) tb=-tb;
for(j=col;j<var+1;j++)
a[i][j]=((a[i][j]*ta)%2-(a[k][j]*tb)%2+2)%2;
}
}
}
for(i=k;i<equ;i++)
if(a[i][col]!=0) return -1;
for(i=0;i<equ;i++)
{
if(!a[i][i])
{
for(j=i+1;j<var;j++)
if(a[i][j]) break;
if(j==var) break;
for(k=0;k<equ;k++)
swap(a[k][i],a[k][j]);
}
}
free_num=k;
if(var-k>0)
{
dfs(var-1);
return ans;
}
if(var-k==0)
{
for(i=k-1;i>=0;i--)
{
int temp=a[i][var]%2;
for(j=i+1;j<var;j++)
if(a[i][j]!=0)
temp=(temp-(a[i][j]*x[j])%2+2)%2;
x[i]=(temp/a[i][i])%2;
}
int sum=0;
for(i=0;i<var;i++) sum+=x[i];
return sum;
}
}
int main()
{
int i,j,k;
char str[20];
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
ans=1000000000;
for(i=0;i<4;i++)
{
cin>>str;
for(j=0;j<4;j++)
{
k=4*i+j;
a[k][k]=1;
if(i>0) a[k][k-4]=1;
if(i<3) a[k][k+4]=1;
if(j>0) a[k][k-1]=1;
if(j<3) a[k][k+1]=1;
if(str[j]=='b') a[k][16]=1;
}
}
for(i=0;i<16;i++)
for(j=0;j<=16;j++)
b[i][j]=a[i][j];
for(k=0;k<16;k++)
b[k][16]^=1;
equ=var=16;
int f1=Gauss();
int min1=ans;
for(i=0;i<16;i++)
for(j=0;j<=16;j++)
a[i][j]=b[i][j];
ans=100000000;
int f2=Gauss();
int min2=ans;
if (f1==-1&&f2==-1) cout<<"Impossible"<<endl;
else cout<<min(ans,min1)<<endl;
return 0;
}
