ac1078.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1078;
const
  maxsize=20;
var
  qx,qy:array[1..sqr(maxsize)]of byte;
  step:array[1..maxsize,1..maxsize]of byte;
  count:array[1..maxsize,1..maxsize]of qword;
  n,m,p,c,i,j,t,f,r:word;
begin
  repeat
    read(n,m,p);c:=0;
    for i:=1 to n do
      for j:=1 to m do begin
        read(t);
        if t=0 then begin
          inc(c);qx[c]:=i;qy[c]:=j;
        end;
      end;

    fillchar(count,sizeof(count),0);
    f:=0;r:=1;step[1,1]:=0;count[1,1]:=1;
    repeat
      repeat
        inc(f);
        for i:=r+1 to c do
          if abs(qx[f]-qx[i])+abs(qy[f]-qy[i])<=p then
            inc(count[qx[i],qy[i]],count[qx[f],qy[f]]);
      until f=r;
      for i:=r+1 to c do
        if count[qx[i],qy[i]]>0 then begin
          inc(r);
          step[qx[i],qy[i]]:=step[qx[f],qy[f]]+1;
          t:=qx[r];qx[r]:=qx[i];qx[i]:=t;
          t:=qy[r];qy[r]:=qy[i];qy[i]:=t;
        end;
    until count[n,m]>0;
    writeln(step[n,m],' ',count[n,m]);
  until seekeof;
end.