$dx = [0,1,0,-1]
$dy = [1,0,-1,0]
def bfs(f, sy, sx, steps, q, r, c)
    for i in 0..3
        cy = sy + $dy[i]
        cx = sx + $dx[i]
        if cy.between?(0,r-1) && cx.between?(0,c-1) && steps[cy][cx]==100000 && f[cy][cx]!="#"
            q.push([cy,cx])
            steps[cy][cx] = steps[sy][sx] + 1
        end
    end
    while q.size > 0
        cy, cx = q.shift
        steps = bfs(f,cy,cx,steps,q,r,c)
    end
    return steps
end