s = gets.chomp.split(" ").map(&:to_i)

$room = [[]]
count = 0
H = s[0]
W = s[1]
K = s[2]
while(s[0] > count)
    a = ""
    a = gets.chomp.split("").map(&:to_s)
    $room[count] = a
    count = count + 1
end
pos = []
$room.each_index { |i| j = $room[i].index 'S'; pos = [i, j] if j }

$k = 0

def rec_memo(i, j, memo_arr)
    $k += 1
    if($k > K * 4)
        print(K)
        exit()
    end
    #print(i,",",j,"\n")
    if (memo_arr[i][j] < 10000)
        memo_arr[i][j]
    end
    if(i > 0 && j > 0 && i+1 < H && j+1 < W)
        res = [ rec_memo(i + 1, j, memo_arr), rec_memo(i - 1, j, memo_arr), rec_memo(i, j + 1, memo_arr), rec_memo(i, j - 1, memo_arr)].min
    end
    print(res)
    if($room[i][j] == "#")
        2
        #memo_arr[i][j] = res
    elsif($room[i][j] == ".")
        1
        #memo_arr[i][j] = res
    end 
end

memo_arr = Array.new(H+1, Array.new(W+1, 10000))

rec_memo(pos[0], pos[1], memo_arr)


