Algoritmos e Estrutura de Dados I - AE22CP - 2013/1

TRABALHO PRÁTICO 1

Bruno César Ribas

Prólogo

Frodo Bolseiro é um jovem e perspicaz Hobbit que recebeu uma nobre, porém complicada, tarefa. A tarefa de destruir o anel de Sauron.

O anel é tão complicado que várias gerações de humanos já o tiveram em seu poder mas nunca o destruíram. O Anel passou a Isildur, que se recusou a destruí-lo, alegando herança de seu reino. Deixou o reino de Gondor para os herdeiros de seu irmão Anárion, pois ele ficaria com Arnor ao norte. Mas quando retornava, foi emboscado por orcs. Pôs o Anel, ficando invisível, e quando tentava atravessar o Anduin, o Anel o traiu, saindo de seu dedo e fazendo-o ser visto. Foi então morto. wikipedia

Muito tempo depois, um pescador ribeirinho chamado Déagol pescava com seu primo Sméagol, quando caiu na água e encontrou o Anel. Sméagol o cobiçou o objeto e matou Déagol enforcado, permanecendo assim com o Um Anel por volta de 500 anos. Então Bilbo, numa aventura com os treze anões, se perdeu, indo parar na caverna de Sméagol (Gollum). Assim encontra o Anel e o guarda. Após vários infortúnios, Bilbo conseguiu escapar da perseguição de Gollum, até que o Anel foi parar no Condado, chegando às mãos de Frodo. wikipedia

Enquanto Frodo segue em sua épica jornada acompanhado do fiel, e muitas vezes o salvador, Sam, os humanos precisam juntar tropas para conseguir lutar contra forças de Sauron que patrulham e exterminam os moradores da terra média.

Nesse momento histórico vamos apenas nos focar nas estratégias para conseguir aumentar o nosso número de tropas. Aragorn o chamou, pessoalmente, para preparar a estratégia para angariar mais tropas em um reino (ou feudo) não muito longe. Mas não se iluda! O caminho é complicado. Muitos Orcs de Sauron estão no caminho e nem sempre teremos a força para batalhar contra essas tropas, por isso uma estratégia é extremamente crucial para sairmos vitoriosos.

A reunião estratégica

Aragorn inicia a nossa reunião abrindo o mapa da Terra Média com os marcadores de tropas que podem se aliar a nós e onde se encontram tropas Orcs. Essas tropas foram identificadas por batedores humanos que bravamente observam a movimentação em terra.

O mapa é bem simples, e você como um Computero moderno já consegue imaginar como representar esse mapa.

O mapa

O mapa da Terra Média é bastante simples suas dimensões nunca extrapolam 500 Linhas por 500 Colunas, pois esse é o máximo que os batedores conseguem avaliar por vez.

Então o mapa é um arquivo de texto onde a primeira linha possui 2 números inteiros L e C indicando, respectivamente, a quantidade de linhas e colunas do mapa.

Sabemos que L e C <= 500

Depois existirão L linhas com C colunas onde cada posição podemos ter algum desses caracteres:

Exemplo de um mapa: 

  10 30
  ##############################
  #...O.......S..O.....RR......#
  #...................R.RR..T..#
  #....................RR......#
  #...RRRPPRR......###..PP.....#
  #..RR.....RR.....#R#..RR.....#
  #.RR.......R.....###.........#
  #RR........RR..O.............#
  #...A......RR.............O..#
  ##############################

Sabemos também que nunca teremos mais que 40000 tropas de Orcs no mapa.

Depois do mapa teremos informações a respeito do tamanho das tropas, tanto nossas como de Orcs e possível aliadas.

A primeira linha após o mapa possui um único número inteiro representando quantas tropas nós temos em nossa posição atual, a próxima linha teremos um único inteiro representando quantas tropas possivelmente aliadas temos (na posição T), teremos N linhas (onde N é a contagem de posições com 'O' no mapa) onde cada possui um único inteiro representando a quantidade de Orcs na posição da ordem da leitura de 'O' no mapa. Então o primeiro número representa a quantidade de orcs na linha 1 coluna 4 (considerando que a linha e coluna começam com índice 0), o segundo número da linha 1 coluna 15, o terceiro numero é da linha 7 coluna 15 e por fim o da linha 8 coluna 26.

Então com todos esses dados o arquivo de entrada ficaria: 

  10 30
  ##############################
  #...O.......S..O.....RR......#
  #...................R.RR..T..#
  #....................RR......#
  #...RRRPPRR......###..PP.....#
  #..RR.....RR.....#R#..RR.....#
  #.RR.......R.....###.........#
  #RR........RR..O.............#
  #...A......RR.............O..#
  ##############################
  1000
  3000
  500
  300
  700
  2000

Movimentação

Sairemos com nossas tropas rumo ao nosso aliado e para isso a movimentação é necessária. Para isso dispomos de alguns comandos:

Cuidado com o Orcs

Atenção, entrar em uma posição com tropas Orcs implica diretamente uma batalha! E batalhas sempre trazem baixas!

Smeagel Traiçoeiro

O Smeagel não é mole não, se você passar no local em que o Smeagel se encontra você perderá 1% de homens da sua tropa a cada 2 movimentações.

Se você for para uma posição onde vai atualizar a perda de 1% de homens por causa do Smeagel e nessa posição existe tropa Orc, você deve primeiro atualizar a perda do Smeagel e depois das tropas.

Por exemplo na situação abaixo: 

  3 10
  ##########
  #AS.O...T#
  ##########
  100
  200
  50

A solução será: 

  direita
  direita
  direita
  direita
  direita
  direita
  direita
  86

Primeiro passa no Smeagel, e logo perde 1%, passando a ficar com 99 homens na tropa. Depois de 2 passos outra perda de 1% do Smeagel, passando para 98 homens e como é uma posição com Orcs acontece uma luta e perdemos 10% (de acordo com as regras da seção anterior). Depois mais 2 passos e perde mais 1% contra o Smeagel, saindo de 88 para 87 homens, e por fim quando chega na posição final perde mais 1% para o Smeagel (por ter andado mais 2 passos) saindo de 87 para 86 homens.

Saída

Execução

A entrada e saída do programa devem ser feitas pela entrada e saída padrão ( como se estivesse lendo as informações pelo teclado e imprimindo na tela)

exemplo de execução: 

  time ./meuprograma < mapa.txt  > solucao.txt

Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "mapa.txt" é o arquivo que contém o mapa da terra média está. O arquivo "solucao" é o arquivo que armazenará a saída do seu programa.

Quando executar o seu programa da forma indicada abaixo , o sinal '<' significa que o conteúdo do 'mapa.txt' será passado ao programa como se ele estivesse sendo lido do teclado. E o sinal '>' significa que tudo que o seu programa imprimir na saída padrão será salvo em 'solucao.txt'. E 'time' é comando que contará o tempo de execução do seu programa.

Exemplos de Entrada e Saída

Não se limite a esses exemplos, crie seus próprios exemplos!

Ranking

O ranking será feito por disputas diárias. Para participar basta enviar o código que o sistema copilará e executará.

Para participar do Ranking o seu código deve funcionar em LINUX, recomendamos o uso do Ubuntu. Se o sistema não conseguir compilar seu programa apenas será avisado que não conseguiu e nada mais.

A sumissão para o Rank é Obrigatória.

No Rank a ordenação será considerada pelo SCORE, definido como: 

  Tropas - Passos-SEM-Smeagel - 2* Passos-COM-Smeagel

Em caso de empate no Score serão considerados os seguintes critérios:

Prazos

Critérios da Correção

---
Last Modified: Wed Jul 31 16:07:34 2013.