LEM2 - GUMBI
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program LEM2;
Const
input = '';
output = '';
maxn = 20;
maxd = 2200000;
Var
n,k: integer;
start,finish: integer;
d,queue: array[0..maxd] of integer;
s: array[1..maxn] of integer;
Procedure init;
Var
f: text;
a,i,j,t: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n, k);
For i:= 1 to n do
Begin
Read(f, a);
s[i]:= 0;
For j:= 1 to a do
Begin
Read(f, t);
s[i]:= s[i] + 1 shl (t - 1);
End;
End;
finish:= 1 shl (k - 1);
start:= 0;
For i:= 1 to n do
Begin
Read(f, t);
If t = 1 then start:= start + 1 shl (i - 1);
End;
Close(f);
End;
Procedure BFS;
Var
front,rear: integer;
u,v,i: integer;
Begin
If start = finish then
Begin
d[start]:= 0;
exit;
End;
Fillchar(d, sizeof(d), 0);
d[start]:= 0;
front:= 1;
rear:= 1;
queue[1]:= start;
Repeat
u:= queue[front];
inc(front);
For i:= 1 to n do
Begin
v:= (u or (1 shl (i - 1))) and (not s[i]);
If (d[v] = 0) and (v <> start) then
Begin
d[v]:= d[u] + 1;
If v = finish then exit;
inc(rear);
queue[rear]:= v;
End;
End;
Until front > rear;
End;
Procedure printresult;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
If (d[finish] = 0) and (finish <> start)
then writeln(f, -1) else writeln(f, d[finish]);
Close(f);
End;
Begin
init;
BFS;
printresult;
End.