Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

Petersen Graph

Enunciado

/*** Autor: Felipe Augusto ***/
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string s;
vector<string> saida;
vector<int> graph[20];
string c = "ABCDEABCDE";
string a = "";

void dfs(int n, int index){
    if(a.size() >= s.size()){
        saida.push_back(a);
        return;
    }

    for(int i = 0; i < graph[n].size(); i++){
        if(s[index] == c[graph[n][i]]){
            a += ('0' + graph[n][i]);
            dfs(graph[n][i], index + 1);
            a.erase(a.size() - 1);
        }
    }
}

int main(){    
    graph[0].push_back(1);
    graph[0].push_back(4);
    graph[0].push_back(5);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[1].push_back(6);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[2].push_back(7);
    graph[3].push_back(2);
    graph[3].push_back(8);
    graph[3].push_back(4);
    graph[4].push_back(0);
    graph[4].push_back(9);
    graph[4].push_back(3);
    graph[5].push_back(8);
    graph[5].push_back(0);
    graph[5].push_back(7);
    graph[6].push_back(8);
    graph[6].push_back(9);
    graph[6].push_back(1);
    graph[7].push_back(9);
    graph[7].push_back(5);
    graph[7].push_back(2);
    graph[8].push_back(5);
    graph[8].push_back(6);
    graph[8].push_back(3);
    graph[9].push_back(7);
    graph[9].push_back(6);
    graph[9].push_back(4);  

    int t;

    scanf("%d", &t);

    while(t--){
        saida.clear();
        cin >> s;

        for(int i = 0; i < 10; i++){
            if(s[0] == c[i]){
                a += ('0' + i);
                dfs(i, 1);
                a.erase(a.size() - 1);
            }
        }

        sort(saida.begin(), saida.end());

        if(saida.size() == 0)
            printf("-1\n");
        else
            cout << saida[0] << endl;
    }

    return 0;
}