// 3 f)

    /**
     * Calcula a forca necessaria que uma personagem e o seu aliado necessita para conquistar um certo local
     * @param p
     * @param origem
     * @param destino
     * @param caminho
     * @return
     */
    public double conquistarLocalComAliado(Personagem p, Local origem, Local destino, LinkedList<Local> caminho) {

        double forcaAlianca = 0;
        Personagem p1 = null;
        Personagem p2 = null;

        Alianca aliancaEscolhida = obterAliancaMaisForte(p);

        // Vai buscar as personagens da aliança
        for (Edge<Personagem, Alianca> edge : mapaAliancas.edges()) {

            if (edge.getElement().equals(aliancaEscolhida)) {
                p1 = edge.getVDest();
                p2 = edge.getVOrig();

                forcaAlianca = (p1.getForca() + p2.getForca()) * aliancaEscolhida.getFatorCompatibilidade();
            }
        }

        // verifica se o local de origem pertence a lista de locais da personagem p
        if (!(p.getListaLocais().contains(origem))) {
            return 0;
        }

        caminho.clear();

        AdjacencyMatrixGraph<Local, Integer> clone = (AdjacencyMatrixGraph<Local, Integer>) mapaEstradas.clone();

        for (Local l : clone.vertices()) {
            if (l.getDono() != null) {
                if (!(l.getNome().equals(origem.getNome()))) {
                    if (l.getDono().getNome().equals(p1.getNome()) || l.getDono().getNome().equals(p2.getNome())) {
                        clone.removeVertex(l);
                    }
                }
            }
        }

        double forcaNecessaria = shortestPathWeightedVertex(clone, origem, destino, caminho);

        if (forcaAlianca > forcaNecessaria) {
            return forcaNecessaria;
        }

        return 0;
    }

    /**
     * Obtem a aliança mais forte de uma personagem
     *
     * @param p
     * @return
     */
    private Alianca obterAliancaMaisForte(Personagem p) {

        List<Personagem> aliados = getAliadosDePersonagem(p);

        double forca = 0;
        Alianca aliancaEscolhida = null;

        for (Personagem aliado : aliados) {
            Alianca c = mapaAliancas.getEdge(p, aliado).getElement();
            Float forcaAlianca = (p.getForca() + aliado.getForca()) * c.getFatorCompatibilidade();

            if (forcaAlianca > forca) {
                aliancaEscolhida = c;
                forca = forcaAlianca;
            }
        }

        return aliancaEscolhida;

    }