import networkx as nx

def crea_graf_laberint(nf, nc):
    g = nx.Graph()
    for f in range(1, nf+1):
        for c in range(1, nc+1):
            g.add_node((f,c))
    for f in range(1, nf+1):
        for c in range(1, nc):
            g.add_edge((f,c), (f, c+1))
    for f in range(1, nf):
        for c in range(1, nc+1):
            g.add_edge((f,c), (f+1, c))
    return g


def afegir_paret(g, a, b):
    if g.has_edge(a,b):
        g.remove_edge(a,b)


def quants_camins(glab, a, b):
    s = 0
    for path in nx.all_simple_paths(glab, a, b):
        s = s + 1
    return s


def afegir_teletransport(glab, a, b):
    glab.add_edge(a, b, tipus='teletransport')


def millor_cami(glab, a, b):
    try:
        cami = nx.shortest_path(glab, a, b)
    except nx.NetworkXNoPath:
        return 'IMPOSSIBLE'
    for i in range(len(cami)-1):
        if glab[cami[i]][cami[i+1]].get('tipus','normal') == 'teletransport':
            return 'TELETRANSPORT'        
    return 'NORMAL'