2608. Duende Perdido

Olá meus amigos nerds. Hoje vamos ajudar um duende a escapar de um complexo de cavernas. Já que é isso que o problema 2608. Duende Perdido nos pede para fazer. Mais especificamente, dado o mapa de um complexo de cavernas, onde estão marcadas as saídas e salões onde o duende não pode visitar, determinar o menor número de salões que o duende tem que passar para poder atingir uma das saídas.

Solução

Podemos resolver esse problema facilmente, se pensarmos nos salões que o duende pode entrar como sendo vértices de um grafo, de modo que os caminhos entre eles sejam as arestas. Assim, a solução do problema seria, simplesmente, computar o caminho mínimo entre a posição atual do duende e uma das saídas. Poderíamos computar o caminho mínimo usando o algoritmo de dijkstra, mas como o tamanho da entrada do problema é pequeno, uma busca em largura é suficiente.

Implementação

844. Número de Erdos

Olá meus amigos nerds. Hoje vamos resolver um dos primeiros problemas que me apresentaram a essa vida de resolver problemas. Vamos tentar descobrir qual é nosso número de Erdos, já que é isso que o problema 844. Número de Erdos nos pede para fazer. Mais especificamente, nossa tarefa é determinar, a partir de uma lista de autores de artigos, o número de Erdos dos autores.

Nesse problema, vale a pena até contar mais um pouco de história. O matemático húngaro Paul Erdos (1913-1996), é considerado o matemático mais prolífico da história, devido ao seu alto número de publicações (mais de 1500). Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado "número de Erdos". Toda pessoa que escreveu um artigo com Erdos tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante. Quando nenhuma ligação pode ser estabelecida entre Erdos e uma pessoa, diz-se que esta possui número de Erdos infinito. Por exemplo, o número de Erdos de Albert Einstein é 2. E, talvez surpreendentemente, o número de Erdos de Bill Gates é 4.

Solução

Outro problema que a solução é uma busca em largura! Mas por motivos históricos, não resisti a tentação de escrever ele. Dado um grafo onde os vértices representam os autores e existe uma aresta entre dois vértices se os autores publicaram juntos, o tamanho do caminho mínimo entre o cada vértice e o vértice que representa Erdos é o número procurado. Como todas as arestas tem o mesmo peso (o grafo não é ponderado), uma simples busca em largura resolve.

Implementação

Que código feio, mas vocês tem que me perdoar já que ele foi escrito há muitos anos atrás.

11006. Colorindo

Olá meus amigos nerds. Dizem que livrinhos de colorir estão na moda hoje em dia. Se isso é verdade eu não sei, mas sei que hoje vamos brincar de colorir alguns, já que é isso que o problema 11006. Colorindo nos pede para fazer. Mais especificamente, dados um desenho quadriculado e um ponto que se deseja começar a colorir, devemos determinar quantos quadrados desse desenho serão coloridos no total sendo que se eu colorir um quadrado devo colorir todos os seus vizinhos a menos que eles já estejam coloridos.

Solução

Esse é um problema bem simples. O processo de colorir descrito no problema é exatamente uma busca em largura, feita sobre o papel quadriculado. Sendo assim basta executarmos a busca e contarmos quantos quadradinhos serão coloridos ao final do processo.

Implementação

Lembram que no problema anterior eu preenchi as bordas da matriz com 0's. Vejam que nesse problema, como eu não fiz isso a cada iteração do loop eu tenho que ficar checando se x e y estão de fato dentro da matriz.

18538. Robô

Olá meus amigos nerds. Hoje vamos determinar onde um robô de limpeza deve parar depois de limpar um salão. Meio chato, mas nem só de coisas legais vive o mundo, né! Já que é isso que o problema 18538. Robô nos pede para fazer. Mais especificamente, dados um mapa indicando a cor de cada ladrilho no chão e a posição inicial do robô, devemos determinar a posição final do robô que só se locomove através de ladrilhos pretos.

Solução

Esse é um problema bem simples. Basta simularmos a trajetória do robô. Para isso, basta ir iterando sobre a posição atual do robô procurando pela próxima posição válida. Para não correr o risco de voltar pelo mesmo caminho que o robô veio, basta ir apagando o caminho a medida que ele vai sendo percorrido.

Implementação

Observe como envolvo a minha matriz com 0's (sentinelas) para evitar que a busca saia dos limites da matriz e eu tenha que ficar verificando isso no código.

819. Pedágio

Olá meus amigos nerds, hoje vamos ajudar Juquinha a decidir quais cidades ele pode visitar. Já que é isso que o problema 819. Pedágio nos pede para fazer. Mais especificamente, dado um mapa com as cidades e estradas, determinar quais cidades são alcançáveis a partir da cidade em que Juquinha se encontra e que o caminho até elas necessite que sejam pagos no máximo P pedágios.

Solução

O problema quase que implora por uma solução usando-se grafos, onde os vértices representam cidades e as arestas rodovias entre elas. Neste grafo o peso de uma aresta representa o custo do pedágio. Assim sendo o problema se reduz ao cálculo do caminho mínimo entre o vértice que representa a cidade onde Juquinha está e todos os outros vértices do grafo.

O caminho mínimo pode ser calculado facilmente usando-se o algoritmo de dijkstra. Hoje estou com pouco tempo, mas outro dia eu ainda quero discutir mais esse, que é um algoritmo muito clássico.

Assim sendo, para resolver o problema basta calcular o caminho mínimo e a resposta será o conjunto de cidades que estão a menos de P pedágios de distância.

P.S. como todos os pesos das arestas são iguais a 1 eu poderia ter simplesmente feito uma busca em largura para calcular a distância, mas resolvi usar dijkstra para deixar a explicação da solução mais simples :).

Implementação

P.S. Não reparem a feiura do código, mas é que eu resolvi esse problema faz muitos anos e fiquei com preguiça de deixar o código mais bonitinho. Pelo menos, observem que realmente melhoramos quando brincamos continuamente de resolver problemas kkk.

8776. Batalha naval

Olá meus amigos nerds, hoje eu peço desculpas a vocês, mas falarei rapidamente sobre um probleminha fácil. Afinal daqui a pouco começa o melhor jogo do ano, a final da Copa do Brasil entre Cruzeiro e Atlético. E como todo bom brasileiro, eu não quero perder essa. Semana que vem, prometo que trago um problema bem mais interessante.

Enquanto esperamos o jogo vamos brincar um pouco de batalha naval? Uma vez que é isso que o problema 8776. Batalha naval nos pede para fazer.  Mais especificamente, o problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determinar o número de navios do outro jogador que foram destruídos.

Solução

Esse problema é bem simples. Para cada posição do mapa, é só verificar se há um navio afundado naquela posição e contar esse navio. Mais algoritmicamente, temos:

cnt = 0
para cada posição do mapa
    if há um navio afundado que ainda não foi contado
        cnt += 1

Para verificar se há um navio afundado em uma posição do mapa é suficiente fazer uma busca em largura a partir daquela posição, ou seja:

vizinhos = fila([posição atual])
afundou = true
while vizinhos não está vazio
    noAtual = vizinhos.top()
    if noAtual não está dentro do mapa
        continue
    if noAtual está intácto
        afundou = false
    else if noAtual recebeu um tiro
        marcar noAtual como visitado
        vizinhos += vizinhos do noAtual 

Implementação

8776. Batalha naval

Olá, estamos aqui de novo para resolver mais problemas! Hoje vamos falar de batalha naval e nos divertir um pouco contando quantos navios conseguimos afundar nesse conhecido jogo, já que é isso que o problema 8776. Batalha naval nos pede. 

Modelagem

Mais especificamente, esse problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determine o número de navios do outro jogador que foram destruídos.

A entrada do problema já nos dá uma boa ideia de como resolvê-lo, basta armazenar o tabuleiro em uma matriz e contar quantos navios foram afundados. Cada posição da matriz pode ser de três tipos: água, navio intacto ou navio avariado por um disparo. Observe que não precisamos armazenar a informação sobre os tiros que acertaram a água.

A restrição de que dois navios não podem ter arestas em comum nos permite aplicar uma busca em largura ao tabuleiro e ir contando quantos navios foram afundados. Não vou explicar, aqui, o que é uma busca em largura já que esse assunto é extensamente abordado em qualquer estudo sobre grafos. Veja que estou apenas pegando emprestada a ideia da busca em largura, mas não estou modelando o problema usando grafos.

Complexidade

Dado um tabuleiro de N x M nossa solução avalia cada posição da matriz uma vez, assim sendo nossa solução é O(N*M).

Implementação

Abaixo uma implementação em c++ do problema. Infelismente, não estou muito inspirado para falar sobre ela já que, como você deve ter visto, o problema é bem simples.