Grafos - LeetCode And Labirinto

Conteúdo da Disciplina: Grafos

Sobre

Este projeto consiste na resolução de questões da plataforma LeetCode na dificuldade difícil. O objetivo é utilizar o conteúdo estudado na disciplina de EDA2.

Foi igualmente implementado um jogo de resolução de labirintos, no qual aplicamos os algoritmos de busca em profundidade (DFS) e busca em largura (BFS).

Questões

Questão	Nível
126. Word Ladder II	Difícil 01
2127. Maximum Employees to Be Invited to a Meeting	Difícil 02
329. Longest Increasing Path in a Matrix	Difícil 03

Contribuidores

Matrícula	Nome	GitHub
202046102	Felipe das Neves Freire	Felipe
222037700	Leonardo de Melo Lima	Leonardo

Linguagem Utilizada

• Python

Uso

Entrar na plataforma LeetCode, procurar pelo nome/número do exercício, colar na aba code e clicar em Submit

Pré-requisitos para o GAME

Para executar o game do labirinto na sua máquina, é necessário ter instalados:

• Python 3.10.0 ou superior
• pygame

Como executar o jogo

No terminal, dentro da pasta do projeto, execute:

python labirinto.py

Tutorial do Game

Antes de iniciar o algoritmo, é possível desenhar o labirinto manualmente:

• Clique com o botão esquerdo do mouse e arraste para desenhar os muros do labirinto;
• Para apagar um muro, use o botão direito do mouse.

Controles do teclado:

• Pressione a tecla b para iniciar o algoritmo BFS;
• Pressione a tecla d para iniciar o algoritmo DFS;
• Pressione a tecla r para reiniciar o jogo.

Observações:

• O algoritmo também pode ser executado sem nenhum muro desenhado;

• Na tela, serão exibidos:

  • o caminho percorrido pelo algoritmo,
  • o tempo de execução,
  • e a quantidade de passos realizados.

Screenshots do LeetCode e do Labirinto

Figura 1: Resultados questão difícil LeetCode 126

Figura 2: Resultados questão difícil LeetCode 126

Figura 3: Resultados questão difícil LeetCode 2127

Figura 4: Resultados questão difícil LeetCode 2127

Figura 5: Resultados questão difícil LeetCode 2127

Figura 6: Resultados questão difícil LeetCode 329

Figura 7: Resultados questão difícil LeetCode 329

Figura 8: Resultados questão difícil LeetCode 329

Figura 9: Código BFS implementado no Labirinto

Figura 10: Código DFS implementado no Labirinto

Vídeo

Explicamos todos os códigos que fizemos na plataforma LeetCode e do Labirinto:

Vídeo do Projeto