讨论 / 为什么无法输出Impossible??????
李军伟 2010-11-01 06:02:00
点我顶贴 收藏 删除
const kk:array [0..15] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768);

var a:array [0..15] of integer;

g:array [0..70000] of boolean;

v:array [1..70000] of longint;

bu:array [1..70000] of longint;

i,j,w,b,head,tail,m,hang,lie:longint;

s:string;

procedure fuzhi(i:longint);

begin

a[i]:=1-a[i];

if (i=1) or (i=2) then begin a[i-1]:=1-a[i-1];a[i+1]:=1-a[i+1];a[i+4]:=1-a[i+4];exit; end;

if (i=4) or (i=8) then begin a[i-4]:=1-a[i-4];a[i+1]:=1-a[i+1];a[i+4]:=1-a[i+4];exit; end;

if (i=7) or (i=11) then begin a[i-4]:=1-a[i-4];a[i-1]:=1-a[i-1];a[i+4]:=1-a[i+4];exit; end;

if (i=13) or (i=14) then begin a[i-1]:=1-a[i-1];a[i-4]:=1-a[i-4];a[i+1]:=1-a[i+1];exit; end;

if (i=0) then begin a[i+1]:=1-a[i+1];a[i+4]:=1-a[i+4]; exit; end;

if (i=3) then begin a[i-1]:=1-a[i-1];a[i+4]:=1-a[i+4];exit;end;

if (i=12) then begin a[i-4]:=1-a[i-4];a[i+1]:=1-a[i+1]; exit; end;

if (i=15) then begin a[i-4]:=1-a[i-4];a[i-1]:=1-a[i-1]; exit; end;

a[i-4]:=1-a[i-4];

a[i-1]:=1-a[i-1];

a[i+1]:=1-a[i+1];

a[i+4]:=1-a[i+4];

end;

procedure zhuanhua(n:longint);

var i:longint;

begin

i:=0;

while n>0 do

begin

a[i]:=n mod 2;

n:=n div 2;

i:=i+1;

end;

end;

begin

{assign(input,'flip.in');reset(input);

assign(output,'flip.out');rewrite(output);}

b:=0;w:=0;

for i:=1 to 4 do

begin

readln(s);

for j:=1 to 4 do

begin

if s[j]='b' then begin b:=b+1;a[(i-1)*4+j-1]:=1; end;

if s[j]='w' then begin w:=w+1;a[(i-1)*4+j-1]:=0; end;

end;

end;

if (b=16) or (w=16) then begin writeln(0);close(input);close(output);exit; end;

//================================bfs========================================

head:=0;

tail:=1;

for i:=0 to 15 do v[1]:=v[1]+a[i]*kk[i];

fillchar(g,sizeof(g),false);

g[v[1]]:=true;

while head<tail do

begin

head:=head+1;

for i:=0 to 15 do

begin

//----------------------------fuzhi------------------------------------------

zhuanhua(v[head]);

fuzhi(i);

//---------------------------------------------------------------------------

m:=0;

for j:=0 to 15 do m:=m+a[j]*kk[j];

if g[m]=false then

begin

g[m]:=true;

tail:=tail+1;

v[tail]:=m;

bu[tail]:=bu[head]+1;

if (m=0) or (m=65535) then begin writeln(bu[tail]);exit; end;

end;

end;

end;

writeln('Impossible');

close(input);close(output);

end.

查看更多回复
提交回复