vijos 1197難解なスイッチ逆bfs+ビット演算
1276 ワード
まずbfsを逆方向にして目標状態から各状態への最小ステップ数を算出し,次に1つ読み込むごとに直接出力すればよい.
コード:
コード:
const
maxm=33554432;
maxn=250000;
var
s,i,j,n,l:longint;
c:char;
v:array[0..maxm] of 0..6;
state,f:array[1..maxn] of longint;
procedure bfs;
var
head,tail,i,u,x:longint;
begin
head:=0;
tail:=1;
state[1]:=1 shl 25-1;
f[1]:=0;
repeat
inc(head);
u:=state[head];
if v[u]=6 then exit;;
for i:=0 to 24 do
begin
x:=u xor (1 shl i);
if i mod 5<>0 then x:=x xor (1 shl (i-1));
if (i+1) mod 5<>0 then x:=x xor (1 shl (i+1));
if i<20 then x:=x xor (1 shl (i+5));
if i>4 then x:=x xor (1 shl (i-5));
if v[x]=0 then
begin
inc(tail);
state[tail]:=x;
v[x]:=v[u]+1;
if x=0 then exit;
end;
end;
until head>=tail;
end;
begin
readln(n);
bfs;
for l:=1 to n do
begin
s:=0;
for i:=1 to 5 do
for j:=1 to 5 do
begin
if j<5
then read(c)
else readln(c);
if c='1' then s:=s+(1 shl ((i-1)*5+j-1));
end;
if l<n then readln;
if s=1 shl 25-1
then writeln(0)
else if v[s]=0
then writeln(-1)
else writeln(v[s]);
end;
end.