Prazo de entrega recomendado:
Você deve auxiliar na preparação de uma partida de RPG. Será necessário abstrair e representar o universo do jogo como um grafo.
Role-Playing Game, ou RPG, é um formato de jogo onde um jogador, o mestre, cria, coordena e planeja os eventos de um universo fictício, enquanto os demais jogadores interpretam personagens dentro desse universo, enfrentando muitos desafios e realizando tarefas através de sua criatividade. Em cada rodada, as habilidades de cada um dos personagem são testadas usando uma combinação de um número sorteado por um dado e dos vários atributos que compõem a personalidade do personagem.
![](rpg_chartacters.jpg)
No Prison Explorer, o universo é um enorme calabouço com várias celas interligadas, cada uma com guardas diferentes e com as mais diversas particularidades. O jogo começa depois de um mercenário ter prendido cada personagem em uma cela distinta. O objetivo é que todos se reencontrem em uma mesma cela depois de um certo número de rodadas. Assim, em conjunto, podem finalmente derrotar o inimigo e se libertar.
Em uma rodada, o mestre desafia cada jogador a mover-se a alguma outra cela descrita no livro. Se vencer, o jogador é libertado de sua cela atual e recebe a chave da nova cela. Nesse momento, são testados os níveis atuais de habilidade nos seis atributos de um personagem: Força, Destreza, Constituição, Inteligência, Sabedoria e Carisma. Os níveis de um personagem no início da rodada correspondem aos níveis mínimos da cela em que ele está atualmente, independentemente do percurso e das rodadas anteriores.
Quando um jogador recebe um desafio, ele lança um dado e pode aumentar algum atributo de seu personagem em até uma unidade. Qual atributo será aumentado vai depender do número sorteado pelo dado. Para vencer o desafio e acessar uma nova cela, o jogador precisa que as habilidades do personagem, depois de aumentado um atributo, tenham pelo menos os níveis mínimos da nova cela — além de interpretar bem o personagem e contar com a sorte, é claro!
Entre as responsabilidades do mestre, está montar o layout do calabouço, selecionando quais celas do livro farão parte do jogo. Cada rodada pode levar desde minutos até horas, então a maior dificuldade é garantir que o jogo não seja impossível de terminar. Por resolver esse problema, como mestre de RPG experiente que é, você gostaria de descobrir em quais celas o jogo pode terminar, de forma que possa ser completado em até duas rodadas.
Entrada
A primeira linha contém o número de celas descritas no livro. Cada uma é representada por uma linha contendo o nome e os níveis mínimos dos atributos associados, em ordem de Força, Destreza, Constituição, Inteligência, Sabedoria e Carisma, conforme exemplo. Em seguida, é dado o número de personagens, cada um representado pelo nome e pelos atributos de sua cela inicial escolhida pelo jogador. Você pode supor que os nomes já estão ordenados.
Exemplo de entrada
6
corredor 3 4 5 3 5 1
galpao-misterioso 3 4 5 4 5 2
quarto-dos-brutos 3 4 4 3 5 2
saguao-dos-tolos 3 3 5 3 5 2
sala-do-chefe 4 4 5 5 5 1
salto-rapido 3 4 5 3 5 2
3
jon 3 4 5 3 5 1
olaf 3 4 4 3 5 2
rufus 3 3 5 3 5 2
Saída
Contém os nomes de todas as celas, em ordem, onde o grupo todo poderá se encontrar após duas rodadas. Se não for possível, então deve conter uma linha Impossivel terminar em duas rodadas.
.
Exemplo de saída
corredor
galpao-misterioso
quarto-dos-brutos
saguao-dos-tolos
salto-rapido
Critérios
Você deve abstrair e representar os dados do problema como um grafo. Antes de escrever seu algoritmo, crie um arquivo grafo.md
com um parágrafo descrevendo muito sucintamente quem são os vértices do grafo e quando há aresta entre dois vértices. Também, tente descrever a saída do problema em termos do grafo que você definiu. Não tente resolver o problema antes de ter certeza de que modelou o problema como um grafo e o descreveu adequadamente. Depois de escrever o algoritmo, implemente um programa em um arquivo rpg.c
.
Correção
Esta tarefa será corrigida automaticamente sempre que você realizar um
git push
. Depois de terminada a tarefa, deve-se utilizar o botão na
interface de notas para solicitar a correção de um monitor.
Turma AB: O peso desta tarefa será 5.