(UVA) 336 - A Node Too Far - Solução

Foi utilizada uma busca implementada por mim.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    void processa() throws NumberFormatException, IOException {
        Scanner scan = new Scanner(System.in);
               
        int caso = 0;
        int qteLigacoes = scan.nextInt();
        while (qteLigacoes != 0) {
            int[][] matriz = new int[30][30];

            int v1;
            int v2;
            int qteA = 0;
            // TreeMap para transformar os nós em índices e poder recuperá-los
            Map<Integer, Integer> mapa = new TreeMap<Integer, Integer>();
            for (int i = 0; i < qteLigacoes; i++) {
                // Pega ligações e atribui '1' na matriz que a simboliza
                v1 = scan.nextInt();    
                if (mapa.get(v1) == null) {
                    mapa.put(v1, qteA);
                    qteA++;
                }
                v2 = scan.nextInt();
                if (mapa.get(v2) == null) {
                    mapa.put(v2, qteA);
                    qteA++;
                }
                matriz[mapa.get(v1)][mapa.get(v2)] = 1;
                matriz[mapa.get(v2)][mapa.get(v1)] = 1;
            }

            // Array para guardar os nós visitados
            ArrayList<Integer> vetorVisitados = new ArrayList<Integer>();
           
            // Lê o nó e o TTL
            v1 = scan.nextInt();
            v2 = scan.nextInt();
            while (v1 != 0 || v2 != 0) {
                caso++;
               
                // Adiciona o nó inicial como visitado
                vetorVisitados.add(mapa.get(v1));

                int contadorB = 1;
               
                // Enquanto não ultrapassou o TTL
                while (contadorB <= v2) {
                    int tamVetor = vetorVisitados.size();
                    for (int i = 0; i < tamVetor; i++) {
                        for (int j = 0; j < mapa.size(); j++) {
                            // Se for a 1a vez, tem que pegar o índice referente ao nó
                            if (i == 0) {
                                if (matriz[mapa.get(v1)][j] == 1) {
                                    if (!vetorVisitados.contains(j)) {
                                        vetorVisitados.add(j);
                                    }
                                }
                            }
                            else if (matriz[vetorVisitados.get(i)][j] == 1) {
                                // Se o nó já foi visitado, não visita
                                if (!vetorVisitados.contains(j)) {
                                    vetorVisitados.add(j);
                                }
                            }
                        }
                    }
                    // Aumenta o TTL
                    contadorB++;
                }
               
                System.out.println("Case " + caso + ": " + (mapa.size()-vetorVisitados.size()) + " nodes not reachable from node " + v1 + " with TTL = " + v2 + ".");
               
                vetorVisitados.clear();
               
                // Lê próximo nó e TTL               
                v1 = scan.nextInt();
                v2 = scan.nextInt();
            }
            // Lê próximo caso           
            qteLigacoes = scan.nextInt();            
        }
                               
        return;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução