Este problema consiste, na implementação de uma lista encadeada com o auxílio de um array (ou vector)

Resolva o problema Quebra-cabeça (OBI2015):


      https://olimpiada.ic.unicamp.br/pratique/p2/2015/f1/quebra/


Este problema consiste, na implementação de uma lista encadeada com o auxílio de um array (ou vector):


Cada peça é formada por 3 campos: [e,c,d] (esquerdo, centro, direito)


O campo central contém uma letra maiúscula, a qual fará parte da “frase secreta” que deverá aparecer depois que o quebra-cabeça estiver montado


Os campos esquerdo e direito são números quaisquer, ≤200000, e são análogos a endereços na memória de um computador


Desta forma, dada uma peça qualquer, representada por [e,c,d] :


O número e representa o “endereço na memória” da peça atual

O campo c é uma letra maiúscula a ser impressa (na ordem certa)

O número d representa o “endereço na memória” da próxima peça na sequência correta que deve ser montada como solução deste quebra-cabeça

A primeira peça da solução do quebra-cabeça está sempre no endereço e=0

O “next” (campo d) da última peça da solução do quebra-cabeça é sempre 1


Por exemplo, no primeiro caso de teste mostrado no enunciado do problema:


  4

  5 A 1 <= final

  0 T 7 <= início

  3 M 5

  7 E 3


A primeira letra da solução é T

O campo “next” desta peça (d) indica que a próxima letra da solução está na peça que está no endereço 7 e vale, portanto, E

Assim por diante, até aparecer o endereço 1 no campo “next”, formando a palavra TEMA


Nesta questão, você deve produzir um programa (em C++) que resolva o problema descrito

Submeta-o no “Pratique” da OBI para que a sua solução seja avaliada


Sugestão de solução:


Crie uma struct Node, análoga ao “node” que usamos em aula:


struct Node {

        char val; // letra da peça

        int next; // "endereço" da próx. peça

};


A principal diferença é que, agora, os endereços serão, simplesmente, índices de um vector de Nodes :


vector<Node> qb (n); // qb[i] == Node (peça) na posição i de qb[]


Crie um mapeamento dos “endereços” e e d nas peças para os índices no vetor qb[]:


Como os índices do vector irão de 0 a n-1 e os “endereços” podem chegar a 200000, o ideal seria utilizar em “hashmap” para o mapeamento [endereço => índice]


Mas, como nós ainda não vimos hashmaps, você pode utilizar um simples vector com todas as possibilidades de endereços (análogo ao problema “Fila”, do trabalho passado):


  vector<int> ind(200000,-1); // mapeamento {endereço->índice em qb[]}


No exemplo acima, teríamos: ind[7] = 3


Leia as n peças da entrada em um “for i” para o vector qb[], tendo o cuidado de guardar o índice i em ind[e]


Agora, é só “percorrer” qb[], analogamente ao que está descrito no item “Percorrendo uma lista”


int p = 0; // “endereço” da primeira peça da solução

while (p != 1) { // 1 é análogo a NULL

          cout << … // imprime val

          p = … // pega o valor do próximo endereço

}