ha:array[0..1000000] of boolean;
a:array[1..4,1..4] of char;
f,fin:Array[1..1000000] of longint;
i,j,n,m,x,y,tt:longint;
function cnt(x,y:longint):longint;
var
t:longint;
begin
if (x=0)or(x=5)or(y=0)or(y=5) then exit(0);
t:=(x-1)*4+y;
exit(1 shl (t-1));
end;
begin
for i:=1 to 4 do
begin
for j:=1 to 4 do
begin
read(a[i,j]);
if a[i,j]='w' then f[1]:=f[1]+cnt(i,j);
end;
readln;
end;
if f[1]=0 then begin writeln(0); halt; end;
ha[f[1]]:=true; fin[1]:=0;
i:=1; j:=1;
while i<=j do
begin
for x:=1 to 4 do
for y:=1 to 4 do
begin
tt:=cnt(x,y)+cnt(x-1,y)+cnt(x+1,y)+cnt(x,y-1)+cnt(x,y+1);
if ha[(tt xor f[i])]=false then
begin
inc(j);
f[j]:=tt xor f[i];
fin[j]:=fin[i]+1;
ha[tt xor f[i]]:=true;
if( tt xor f[i]=0) then
begin
writeln(fin[j]);
halt;
end;
end;
end;
inc(i);
end;
writeln('impossible');
end.
此题直接广搜,算不是太难,没必要用位运算+hash。
判断(含边界条件)后将四边的全换,
存储(避免重复);
不用800ms,
即可ac。