def min_time(x):
    'my lib'
    graph = GeometryTopology.Graph()
    for i in range(h):
        for j in range(w):
            graph.add_node((i, j))
    for i in range(h):
        for j in range(w):
            if (i > 0):
                graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
            if (i < (h - 1)):
                graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
            if (j > 0):
                graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
            if (j < (w - 1)):
                graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
    return graph.dijkstra(source)[target]
    'networkx'
    graph = nx.DiGraph()
    for i in range(h):
        for j in range(w):
            if (i > 0):
                graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
            if (i < (h - 1)):
                graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
            if (j > 0):
                graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
            if (j < (w - 1)):
                graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
    return nx.dijkstra_path_length(graph, source, target)
    return nx.astar_path_length(graph, source, target, heuristic_function)
my lib
def min_time(x):
    
    graph = GeometryTopology.Graph()
    for i in range(h):
        for j in range(w):
            graph.add_node((i, j))
    for i in range(h):
        for j in range(w):
            if (i > 0):
                graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
            if (i < (h - 1)):
                graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
            if (j > 0):
                graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
            if (j < (w - 1)):
                graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
    return graph.dijkstra(source)[target]
    'networkx'
    graph = nx.DiGraph()
    for i in range(h):
        for j in range(w):
            if (i > 0):
                graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
            if (i < (h - 1)):
                graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
            if (j > 0):
                graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
            if (j < (w - 1)):
                graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
    return nx.dijkstra_path_length(graph, source, target)
    return nx.astar_path_length(graph, source, target, heuristic_function)