Conteúdo da Disciplina: Grafos 01
Este projeto consiste na resolução de questões da plataforma HackerRank variando nas dificuldades de médio e difícil. O objetivo é utilizar o conteúdo estudado.
Fizemos também um game com a proposta de solução de um labirinto utilizando DFS e BFS.
| Questão | Nível |
|---|---|
| BFS: Crab Graphs | Médio |
| BFS: Shortest Reach in a Graph | Difícil |
| Matrícula | Nome | GitHub |
|---|---|---|
| 202046102 | Felipe das Neves Freire | Felipe |
| 222037700 | Leonardo de Melo Lima | Leonardo |
- Python
Entrar na plataforma HackerRank, procurar pelo nome/número do exercício, colar na aba code e clicar em Run Code
Para rodar o game, é necessário que essas dependências estejam instaladas na sua máquina:
- Python 3.10.0 (ou superior)
- pygame
python labirinto.py
Para jogar, é necessário primeiro desenhar o labirinto, para isso, basta clicar com o botão esquerdo do mouse e arrastar para desenhar os muros. Para apagar basta clicar com o botão direito do mouse.
-
O algoritmo também pode ser iniciado sem ter desenhados os muros;
-
Utilize a letra "b" para inicial o algoritmo BFS e a letra "d" para inicializar o algoritmo DFS;
-
Utilize a leta "r" para reiniciar o jogo.
Nas telas será mostrado o caminho percorrido pelo algoritmo. Além do tempo de execução do algoritmo. E o número de passos percorridos.
Na figura 1 apresentamos a tela inicial do game, onde é possível construir os muros do labirinto clicando com o botão esquerdo do mouse, se necessário pode-se apagar as parades clicando com o botão direito do mouse.
Figura 1: Tela inicial de desenho dos muros
Na figura 2 apresentamos a tela que ao clicar na letra B é iniciado o algoritmo BFS que percorrerá o labirinto marcando de azul os nós visitados, ao encontrar o nó "end", que é o nó representando a saída do labirinto, o algoritmo dará o menor caminho possível representado pela cor amarela.
Figura 2: Tela BFS
Na figura 3 apresentamos a tela que ao clicar na ledra D é iniciado o algoritmo DFS que percorrerá o labirinto marcando de azul os nós visitados, ao encontrar o nó "end", que é o nó representando a saída do labirinto, o algoritmo dará o caminho possível representado também pela cor amarela.
Figura 3: Tela DFS
Figura 4: Resultados questão difícil rackerRank
Figura 5: Resultados questão difícil rackerRank
Figura 6: Resultados questão média rackerRank
Figura 7: Resultados questão média rackerRank
Explicamos o funcionamento do jogo e do código de nível difécil do HackerRank, como estava difícil de encaixar a explicação da questão média preferimos focar na explicação dos problemas de maior dificuldade.
| Vídeo 01 |
|---|
| HackerRank Problem + Labyrinth Game |