var b,bb:array[1..800,1..800]of boolean;
    a:array[1..800,1..800]of longint;
    x,y,i,j,h,w,k,sx,sy,ans:longint;
    ch:char;
function min(a,b,c,d,e:longint):longint;
begin
    if(a<b)and(a<c)and(a<d)and(a<e)then exit(a)
    else if(b<c)and(b<d)and(b<e)then exit(b)
    else if(c<d)and(c<e)then exit(c)
    else if d<e then exit(d)else exit(e);
end;
procedure pp(x,y,p:longint);
begin
    ans:=min(ans,x-1,y-1,h-x,w-y);bb[x,y]:=true;
    if(x+1)<=h then if(not b[x+1,y])and(p<k)and(not bb[x+1,y])then pp(x+1,y,p+1);
    if(x-1)>0 then if(not b[x-1,y])and(p<k)and(not bb[x-1,y])then pp(x-1,y,p+1);
    if(y+1)<=w then if(not b[x,y+1])and(p<k)and(not bb[x,y+1])then pp(x,y+1,p+1);
    if(y-1)>0 then if(not b[x,y-1])and(p<k)and(not bb[x,y-1])then pp(x,y-1,p+1);
end;
procedure init;
begin
    readln(h,w,k);
    for i:=1 to h do begin
    for j:=1 to w do begin
        read(ch);
        if ch='S'then begin
            sx:=i;sy:=j;
        end else if ch='#'then b[i,j]:=true;
    end;readln;
    end;
end;
begin
    fillchar(b,sizeof(b),false);
    fillchar(bb,sizeof(bb),false);
    init;
    ans:=maxlongint;
    pp(sx,sy,0);
    if(sx=1)or(sx=h)or(sy=w)or(sy=1)then writeln('0')else
    if ans mod k<>0 then writeln((ans+k) div k+1) else writeln(ans div k+1);
end.
                    

Galaxy Online Judge System

