简单枚举。
每个格子只有翻与不翻两种状态(翻两次跟没翻一样)。总共16个格子，最多只能翻出2^16种状态。
Code:
[cpp] #include
bool s[20][20];
int best;
int check()
{
int i, j, tot = 0;
for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j];
if(tot == 0 || tot == 16) return 1;
return 0;
}
void Echange(int x, int y)
{
s[x][y] = !s[x][y];
s[x+1][y] = !s[x+1][y];
s[x][y+1] = !s[x][y+1];
if(x>0) s[x-1][y] = !s[x-1][y];
if(y>0) s[x][y-1] = !s[x][y-1];
}
void Search(int k, int ans)
{
int x, y;
if(16 == k) {
if( check()&& ans
x = k /4;
y = k %4;
Search(k+1,ans);//不翻
Echange(x, y);
Search(k+1,ans+1);//翻
Echange(x, y);
}
}
void work()
{
int i, j;
char c;
for(i = 0; i<4; i++)
{
for(j = 0; j<4; j++){
scanf("%c", &c);
if(c=='w') s[i][j] = 0;
else s[i][j] = 1;
}
getchar();
}
//for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("\n");}
best = 1000;
Search(0, 0);
for(i=0;i<4;i++)
for(j=0;j<4;j++)
s[i][j] =!s[i][j];
Search(0, 0);
if(best != 1000) printf("%d\n",best);
else printf("Impossible\n");
}
int main()
{
work();
return 0;
}
#include
bool s[20][20];
int best;
int check()
{
int i, j, tot = 0;
for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j];
if(tot == 0 || tot == 16) return 1;
return 0;
}
void Echange(int x, int y)
{
s[x][y] = !s[x][y];
s[x+1][y] = !s[x+1][y];
s[x][y+1] = !s[x][y+1];
if(x>0) s[x-1][y] = !s[x-1][y];
if(y>0) s[x][y-1] = !s[x][y-1];
}
void Search(int k, int ans)
{
int x, y;
if(16 == k) {
if( check()&& ans
x = k /4;
y = k %4;
Search(k+1,ans);//不翻
Echange(x, y);
Search(k+1,ans+1);//翻
Echange(x, y);
}
}
void work()
{
int i, j;
char c;
for(i = 0; i<4; i++)
{
for(j = 0; j<4; j++){
scanf("%c", &c);
if(c=='w') s[i][j] = 0;
else s[i][j] = 1;
}
getchar();
}
//for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("\n");}
best = 1000;
Search(0, 0);
for(i=0;i<4;i++)
for(j=0;j<4;j++)
s[i][j] =!s[i][j];
Search(0, 0);
if(best != 1000) printf("%d\n",best);
else printf("Impossible\n");
}
int main()
{
work();
return 0;
}