eval"H,W,K="+gets.split*?,;
A=*$<,?#*m=$$;
q=[[A.index{|l|J=l=~/S/},J]];
0.upto(K){
r,q=q,[];
r.map{|y,x|
A[y][x]>?#&&
-2.step(5,2){|j|
q<<[y+j%3-1,x+j/3]
}+
m=[m,y,H+~y,x,W+~x].min;
A[y][x]=?#
}
};
p~-m/K+2
