来自"NOCOW"

我的应该是看起来最舒服的吧

#include <cstdio>
#include <cstring>
 
int s[5][5],tmp[5][5],dir[5][2],a[5],ans,b[5];
char ch[5][5];
bool tt=false;
 
inline void Change(int x,int y){
	tmp[x][y]^=1;
	for (int i=1;i<=4;i++){
		int fx=x+dir[i][0],fy=y+dir[i][1];
		if (fx>0 && fx<=4 && fy>0 && fy<=4)
			tmp[fx][fy]^=1;
	}
}
 
void Search(int k){
	if (k>4){
		for (int i=1;i<=4;i++)
			memcpy(tmp,s,sizeof tmp);
		memcpy(a,b,sizeof a);
		int sum=0,j;
		for (int i=1;i<=4;i++){
			j=0;
			while (a[i]){
				j++;
				if (a[i]&1){
					sum++;
					Change(i,j);
				}
				a[i]/=2;
			}
		}
		for (int i=1;i<=4;i++)
		for (int j=1;j<=4;j++)
		if (tmp[i][j]!=tmp[1][1])	return;
		tt=true;
		if (sum<ans)	ans=sum;
		return;
	}
	for (int i=0;i<1<<4;i++){
		b[k]=i;
		Search(k+1);
	}
}
 
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
 
	dir[1][0]=0,dir[2][0]=0,dir[3][0]=1,dir[4][0]=-1;
	dir[1][1]=1,dir[2][1]=-1,dir[3][1]=0,dir[4][1]=0;
 
	for (int i=1;i<=4;i++)
		scanf("%s",&ch[i]);
	for (int i=1;i<=4;i++)
	for (int j=1;j<=4;j++)
		s[i][j]=(ch[i][j-1]=='b');
 
	ans=2134000000;
	Search(1);
 
	if (tt)	printf("%d\n",ans);
	else	printf("Impossible\n");
 
	return 0;
}

暴搜AC,看了看下面的程序，还是我的最清楚易懂

#include<iostream>
using namespace std;
long s,m=99999999;
long a[5][5]={0},g[5][5]={0};
void deal(int x,int y,int i)
{
    if (i==1)
    {
        g[x][y]=abs(g[x][y]-1);
        g[x+1][y]=abs(g[x+1][y]-1);
        g[x-1][y]=abs(g[x-1][y]-1);
        g[x][y+1]=abs(g[x][y+1]-1);
        g[x][y-1]=abs(g[x][y-1]-1);
        ++s;
    }
}
bool judge()
{
    int i,j;
    bool b=true;
    for (i=1;i<=4;++i)
    for (j=1;j<=4;++j)
     if (g[i][j]!=0) b=false;
    if (b==true) return true;
    for (i=1;i<=4;++i)
    for (j=1;j<=4;++j)
     if (g[i][j]!=1) return false;
    return true;
}    
int main(void)
{
    long i,j;
    char c;
    for (i=1;i<=4;++i)
     for (j=1;j<=4;++j)
      {
          cin>>c;
          if (c=='b') a[i][j]=1;
          else        a[i][j]=0;
      }    
    long i1,i2,i3,i4,
         i5,i6,i7,i8,
         i9,i10,i11,i12,
         i13,i14,i15,i16;
    for (i1=0;i1<=1;i1++)
    for (i2=0;i2<=1;i2++)
    for (i3=0;i3<=1;i3++)
    for (i4=0;i4<=1;i4++)
    for (i5=0;i5<=1;i5++)
    for (i6=0;i6<=1;i6++)
    for (i7=0;i7<=1;i7++)
    for (i8=0;i8<=1;i8++)
    for (i9=0;i9<=1;i9++)
    for (i10=0;i10<=1;i10++)
    for (i11=0;i11<=1;i11++)
    for (i12=0;i12<=1;i12++)
    for (i13=0;i13<=1;i13++)
    for (i14=0;i14<=1;i14++)
    for (i15=0;i15<=1;i15++)
    for (i16=0;i16<=1;i16++)
     {
         s=0;
         for (i=1;i<=4;i++)
         for (j=1;j<=4;j++)
          g[i][j]=a[i][j];
         deal(1,1,i1);
         deal(1,2,i2);
         deal(1,3,i3);
         deal(1,4,i4);
         deal(2,1,i5);
         deal(2,2,i6);
         deal(2,3,i7);
         deal(2,4,i8);
         deal(3,1,i9);
         deal(3,2,i10);
         deal(3,3,i11);
         deal(3,4,i12);
         deal(4,1,i13);
         deal(4,2,i14);
         deal(4,3,i15);
         deal(4,4,i16);
         if ((judge()==true) && (s<m)) m=s;
     }    
     if (m==99999999) cout<<"Impossible"<<"\n";
     else cout<<m<<"\n";
     return 0;
}    
 
from chuchill

---

Solution From Xcheng

枚举第一行的状态（DFS），然后从第二行起根据上一行的情况确定是否PRESS。

---

---

Solution From yiyi

同一硬币硬币翻2次还原,只需确定16个硬币中哪些被选择翻过. 枚举,使用位运算,共65536种状态.棋盘也转为16位二进制数. 用时:0.031s; 内存:208KB 具体实现,见代码:

prograM u1060;
var
  c,i,k,t,ans,x:longint;
  s:string[7];
begin
  ans:=-1; c:=0;
  for i:=1 to 4 do
    begin
      readln(s);
      for k:=1 to 4 do
        if s[k]='b' then c:=c or (1<<(k+ans));
      inc(ans,4);
    end;
  if (c=0) or (c=$ffff) then begin write('0'); halt(0) end;
  ans:=17;
  for k:=1 to 1<<16-1 do
    begin
      t:=c;
      if (k and (1<<0))<>0 then
        begin
          t:=t xor 1<<0;
          t:=t xor 1<<1;
          t:=t xor 1<<4;
        end;
      if (k and (1<<1))<>0 then
        begin
          t:=t xor 1<<0;
          t:=t xor 1<<1;
          t:=t xor 1<<2;
          t:=t xor 1<<5;
        end;
      if (k and (1<<2))<>0 then
        begin
          t:=t xor 1<<1;
          t:=t xor 1<<2;
          t:=t xor 1<<3;
          t:=t xor 1<<6;
        end;
      if (k and (1<<3))<>0 then
        begin
          t:=t xor 1<<2;
          t:=t xor 1<<3;
          t:=t xor 1<<7;
        end;
      if (k and (1<<4))<>0 then
        begin
          t:=t xor 1<<0;
          t:=t xor 1<<4;
          t:=t xor 1<<5;
          t:=t xor 1<<8;
        end;
      if (k and (1<<5))<>0 then
        begin
          t:=t xor 1<<1;
          t:=t xor 1<<4;
          t:=t xor 1<<5;
          t:=t xor 1<<6;
          t:=t xor 1<<9;
        end;
      if (k and (1<<6))<>0 then
        begin
          t:=t xor 1<<2;
          t:=t xor 1<<5;
          t:=t xor 1<<6;
          t:=t xor 1<<7;
          t:=t xor 1<<10;
        end;
      if (k and (1<<7))<>0 then
        begin
          t:=t xor 1<<3;
          t:=t xor 1<<6;
          t:=t xor 1<<7;
          t:=t xor 1<<11;
        end;
      if (k and (1<<8))<>0 then
        begin
          t:=t xor 1<<4;
          t:=t xor 1<<8;
          t:=t xor 1<<9;
          t:=t xor 1<<12;
        end;
      if (k and (1<<9))<>0 then
        begin
          t:=t xor 1<<5;
          t:=t xor 1<<8;
          t:=t xor 1<<9;
          t:=t xor 1<<10;
          t:=t xor 1<<13;
        end;
      if (k and (1<<10))<>0 then
        begin
          t:=t xor 1<<6;
          t:=t xor 1<<9;
          t:=t xor 1<<10;
          t:=t xor 1<<11;
          t:=t xor 1<<14;
        end;
      if (k and (1<<11))<>0 then
        begin
          t:=t xor 1<<7;
          t:=t xor 1<<10;
          t:=t xor 1<<11;
          t:=t xor 1<<15;
        end;
      if (k and (1<<12))<>0 then
        begin
          t:=t xor 1<<8;
          t:=t xor 1<<12;
          t:=t xor 1<<13;
        end;
      if (k and (1<<13))<>0 then
        begin
          t:=t xor 1<<9;
          t:=t xor 1<<12;
          t:=t xor 1<<13;
          t:=t xor 1<<14;
        end;
      if (k and (1<<14))<>0 then
        begin
          t:=t xor 1<<10;
          t:=t xor 1<<13;
          t:=t xor 1<<14;
          t:=t xor 1<<15;
        end;
      if (k and (1<<15))<>0 then
        begin
          t:=t xor 1<<11;
          t:=t xor 1<<14;
          t:=t xor 1<<15;
        end;
      if (t=0) or (t=$ffff) then
        begin
          x:=k;
          x:=(x and $55555555) + ((x>>1) and $55555555);
          x:=(x and $33333333) + ((x>>2) and $33333333);
          x:=(x and $0f0f0f0f) + ((x>>4) and $0f0f0f0f);
          x:=(x and $00ff00ff) + ((x>>8) and $00ff00ff);
          x:=(x and $0000ffff) + ((x>>16) and $0000ffff);
          if x<ans then ans:=x
        end;
    end;
  if ans=17
    then writeln('Impossible')
    else writeln(ans)
end.

---

裸搜就可以过,代码没有楼上恐怖

program cao;
const
  maxn=4;
  dx:array[1..5] of longint=(0,0,1,0,-1);
  dy:array[1..5] of longint=(0,1,0,-1,0);
 
var
  map,can:array[0..maxn,0..maxn] of boolean;
  a,b,c,d,e,f,g,h,i,j,k,l,n,m,p,q,ans:longint;
  ch:char;
 
procedure init;
begin
  for i:=1 to maxn do
  begin
    for j:=1 to maxn do
    begin
      read(ch);
      map[i,j]:=ch=‘b’;
    end;
    readln;
  end;
  for i:=1 to maxn do
    for j:=1 to maxn do
      can[i,j]:=true;
end;
 
procedure search(x,y,depth,last:longint);
var
  i,j:longint;
begin
 // writeln(x,’ ‘,y);
  if depth>=ans then exit;
  if (last=0)or(last=16) then
  begin
    if depth<ans then ans:=depth;
    exit;
  end;
  inc(y);
  if y>maxn then
  begin
    y:=1;
    inc(x);
  end;
  if x>maxn then exit;
  search(x,y,depth,last);
  for i:=1 to 5 do
    if can[x+dx[i],y+dy[i]] then
    begin
      map[x+dx[i],y+dy[i]]:=not(map[x+dx[i],y+dy[i]]);
      if map[x+dx[i],y+dy[i]] then dec(last) else inc(last);
    end;
  search(x,y,depth+1,last);
  for i:=1 to 5 do
    if can[x+dx[i],y+dy[i]] then
    begin
      map[x+dx[i],y+dy[i]]:=not(map[x+dx[i],y+dy[i]]);
      if map[x+dx[i],y+dy[i]] then dec(last) else inc(last);
    end;
end;
 
procedure main;
begin
  m:=0;
  for i:=1 to maxn do
    for j:=1 to maxn do
      if map[i,j]=false then inc(m);
  ans:=maxlongint;
  search(1,0,0,m);
end;
 
procedure print;
begin
  if ans=maxlongint then writeln(‘Impossible’)
  else writeln(ans);
end;
 
begin
  init;
  main;
  print;
end.

---

ls的各位不觉得这题跟1042是一样的么？ --Wecing 21:51 2010年4月20日 (CST)

---

Orz Wecing

---

暴强的程序（非原创）

program cyd;
  var
    v:array[0..65535]of boolean;
    q:array[0..65535]of word;
    l:array[0..65535]of byte;
    map:array[1..4,1..4]of boolean;
    front,rear,s:word;
    i,j,x,y:byte;
    c:char;
  procedure flip(x,y:byte);
    begin
      if (x>0) and (x<5) and (y>0) and (y<5) then
        map[x,y]:=not map[x,y];
    end;
  begin
    q[0]:=0;
    for i:=1 to 4 do
      begin
        for j:=1 to 4 do
          begin
            read(c);
            q[0]:=q[0]*2;
            if c='b' then inc(q[0]);
          end;
      readln;
    end;
    fillchar(v,sizeof(v),0);
    front:=0;
    rear:=0;
    v[q[0]]:=true;
    l[q[0]]:=0;
    repeat
      for i:=1 to 4 do
        for j:=1 to 4 do
          begin
            s:=q[front];
            for x:=4 downto 1 do
              for y:=4 downto 1 do
                begin
                  map[x,y]:=odd(s);
                  s:=s div 2;
                end;
            flip(i,j);
            flip(i-1,j);
            flip(i+1,j);
            flip(i,j-1);
            flip(i,j+1);
            s:=0;
            for x:=1 to 4 do
              for y:=1 to 4 do
                s:=s*2+ord(map[x,y]);
            if not v[s] then
              begin
                v[s]:=true;
                inc(rear);
                q[rear]:=s;
                l[s]:=l[q[front]]+1;
              end;
          end;
      inc(front);
    until (front>rear) or v[0] or v[65535];
    if front>rear then
      writeln('Impossible') else
    if v[0] then writeln(l[0]) else writeln(l[65535]);
  end.

我整成高斯消元了……

/*
PROB: URAL 1060
LANG: C++
AUTHOR: mato_no1
*/
#include <stdio.h>
#include <string.h>
#include <bitset>
#define re(i, l, r) for (int i=l; i<r; i++)
#define rre(i, r, l) for (int i=r; i>=l; i--)
using std::bitset;
const int n = 16, P[n] = {19, 39, 78, 140, 305, 626, 1252, 2248, 4880, 10016, 20032, 35968, 12544, 29184, 58368, 51200}, INF = 1000000000;
bool a[n], b[n][n + 1];
int res = INF;
void init(void)
{
     re(i, 0, n) {a[i] = getchar() == 'b'; if (i % 4 == 3) char ch = getchar();}
}
void swap(int i, int j)
{
     int t;
     re(k, i, n+1) {t = b[i][k]; b[i][k] = b[j][k]; b[j][k] = t;}
}
void xx2(int v, int sum)
{
     if (sum >= res) return;
     if (v < 0) {res = sum; return;}
     if (b[v][v]) {
        rre(i, v-1, 0) if (b[i][v]) b[i][n] ^= b[v][n];
        xx2(v - 1, sum + b[v][n]);
        rre(i, v-1, 0) if (b[i][v]) b[i][n] ^= b[v][n];
     } else {
        xx2(v - 1, sum);
        rre(i, v-1, 0) if (b[i][v]) b[i][n] ^= 1;
        xx2(v - 1, sum + 1);
        rre(i, v-1, 0) if (b[i][v]) b[i][n] ^= 1;
     }
}        
void xx1(void)
{
     re(i, 0, n-1) {
       if (!b[i][i]) {
          int x = -1; re(j, i+1, n) if (b[j][i]) {x = j; break;}
          if (x >= 0) swap(i, x); else continue;
       }
       re(j, i+1, n) if (b[j][i]) re(k, i, n+1) b[j][k] ^= b[i][k];
     }
     re(i, 0, n) {bool ff = false; re(j, 0, n) ff |= b[i][j]; if (!ff && b[i][n]) return;}
     xx2(n - 1, 0);
}
void xxx(void)
{
     memset(b, false, sizeof(b));
     re(i, 0, n) {bitset <32> x = P[i]; re(j, 0, n) b[i][j] = x[j]; b[i][n] = a[i];}
     xx1();
     re(i, 0, n) {bitset <32> x = P[i]; re(j, 0, n) b[i][j] = x[j]; b[i][n] = !a[i];}
     xx1();
}
int main(void)
{
    init();
    xxx();
    if (res == INF) puts("Impossible"); else printf("%d\n", res);
    return 0;
}