传送门 状态数小于2^16，考虑状压。 然后枚举出发点与到达点，spfa水过。 时间：2^16(状态）*16点数*4方案数。
var pow:array [0..20] of longint; vi,q:array [0..100005] of longint; st,en,i,h,t,x:longint; ch:char; begin st:=0; pow[1]:=1; for i:=2 to 16 do pow[i]:=pow[i-1]*2; for i:=1 to 16 do begin read(ch); if (ch='1') then st:=st+pow[i]; if (i mod 4=0) then readln; end; readln; en:=0; for i:=1 to 16 do begin read(ch); if (ch='1') then en:=en+pow[i]; if (i mod 4=0) then readln; end; fillchar(vi,sizeof(vi),1); vi[st]:=0; q[1]:=st; h:=0; t:=1; while (h<t) do begin inc(h); x:=q[h]; for i:=1 to 16 do if (x and pow[i]<>0) then begin if (i mod 4<>1) and (x and pow[i-1]=0) and (vi[x-pow[i]+pow[i-1]]>vi[x]+1) then begin vi[x-pow[i]+pow[i-1]]:=vi[x]+1; inc(t); q[t]:=x-pow[i]+pow[i-1]; end; if (i mod 4<>0) and (x and pow[i+1]=0) and (vi[x-pow[i]+pow[i+1]]>vi[x]+1) then begin vi[x-pow[i]+pow[i+1]]:=vi[x]+1; inc(t); q[t]:=x-pow[i]+pow[i+1]; end; if (i>=5) and (x and pow[i-4]=0) and (vi[x-pow[i]+pow[i-4]]>vi[x]+1) then begin vi[x-pow[i]+pow[i-4]]:=vi[x]+1; inc(t); q[t]:=x-pow[i]+pow[i-4]; end; if (i<=12) and (x and pow[i+4]=0) and (vi[x-pow[i]+pow[i+4]]>vi[x]+1) then begin vi[x-pow[i]+pow[i+4]]:=vi[x]+1; inc(t); q[t]:=x-pow[i]+pow[i+4]; end; end; end; write(vi[en]); end.