這個跟暑假做的一個題目是類似的 不過就是多了一種可能 全黑或者全白都可以
算法思路：
1 第一行枚舉操作 下面的每行如果上行此列為黑（或者白）的時候進行操作
2 檢查最后一行是否滿足要求
剪枝：
如果操作次數已經超過當前最小次數 不必再試驗
代碼如下：
#include "stdio.h"
#include "memory.h"
#define INF 32675
int grid[4][4],a[4][4],out[4][4],op[4][4];
char cgrid[4][4];
void next()
{
int j;
for(j=3;j>=0;j--)
{
if(j==3) op[0][j]++;
else
if(op[0][j+1]==2) {op[0][j+1]=0;op[0][j]++;}
else break;
}
}
void copy()
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
a[i][j]=grid[i][j];
}
void change(int i,int j)
{
a[i][j]^=1;
if(j>0) a[i][j-1]^=1;
if(j<3) a[i][j+1]^=1;
if(i>0) a[i-1][j]^=1;
if(i<3) a[i+1][j]^=1;
}
int main()
{
int i,j,cnt,min=INF,flag;
for(i=0;i<4;i++)
{
gets(cgrid[i]);
for(j=0;j<4;j++)
{
if(cgrid[i][j]=='w') grid[i][j]=0;
else grid[i][j]=1;
}
}
memset(op,0,sizeof(op));
while(op[0][0]!=2)
{
copy();
cnt=0;
flag=0;
for(i=0;i<=4;i++)
{
if(i!=0&&i!=4)
{
for(j=0;j<4;j++)
if(a[i-1][j]==1)
{
op[i][j]=1;
change(i,j);
cnt++;
if(cnt>min) {flag=1;break;}
}
else op[i][j]=0;
}
else
{
if(i==0)
{
for(j=0;j<4;j++)
if(op[i][j]==1)
{
change(i,j);cnt++;
}
}
else
if(i==4)
{
for(j=0;j<4&&a[i-1][j]==0;j++);
if(j==4&&cnt<min) {min=cnt;copy();}
}
}
if(flag==1) break;
}
next();
}
memset(op,0,sizeof(op));
while(op[0][0]!=2)
{
copy();
cnt=0;
flag=0;
for(i=0;i<=4;i++)
{
if(i!=0&&i!=4)
{
for(j=0;j<4;j++)
if(a[i-1][j]==0)
{
op[i][j]=1;
change(i,j);
cnt++;
if(cnt>min) {flag=1;break;}
}
else op[i][j]=0;
}
else
{
if(i==0)
{
for(j=0;j<4;j++)
if(op[i][j]==1)
{
change(i,j);cnt++;
}
}
else
if(i==4)
{
for(j=0;j<4&&a[i-1][j]==1;j++);
if(j==4&&cnt<min) {min=cnt;copy();}
}
}
if(flag==1) break;
}
next();
}
if(min==INF) printf("Impossible\n");
else
printf("%d\n",min);
// while(1);
return 0;
}