🏰 Clockwork Guardian 🤖

🗡️ Sinopse

No coração da Skywatch Spire de Eldoria, um desafio traiçoeiro nos aguarda! 🌪️ Os outrora leais Clockwork Sentinels 🤖 se voltaram contra nós, transformando a torre em um labirinto perigoso. 😱 Nossa missão é navegar pela grade hostil, evitando os sentinelas (1’s) e encontrando o caminho mais curto para a saída (‘E’). 🏃‍♂️💨 Armados com o poder do Breadth-First Search (BFS) 🔍, exploraremos cada canto para determinar a rota de fuga ideal! 🗺️✨

📜 Descrição

Imagine-se subindo a Skywatch Spire, uma torre outrora majestosa agora dominada por Clockwork Sentinels rebeldes. 🏰🤖 Cada nível é uma grade 2D, onde caminhos abertos são marcados como 0, sentinelas hostis como 1 e a saída como ‘E’. 🔢 Começando do canto superior esquerdo (0,0), nosso objetivo é encontrar o caminho livre de sentinelas mais curto até a saída. 🎯

Este é um problema clássico de caminho mais curto em uma grade, e o BFS é nosso fiel aliado! 🤝 Ao explorar células em ordem crescente de distância a partir do início, o BFS garante encontrar a rota mais curta. 🧭 Nossa tarefa é implementar este algoritmo de pathfinding, navegando pela grade passo a passo, até alcançarmos a saída ou determinarmos que a fuga é impossível. ⚠️

🛡️ Habilidades Necessárias

Para conquistar este labirinto mecânico, você precisará de:

• 🧠 Sólida compreensão de algoritmos de travessia de grafos, especialmente BFS
• 🗺️ Familiaridade com problemas de pathfinding baseados em grade
• 🎲 Conforto com manipulação de arrays 2D
• 🚧 Capacidade de traduzir restrições do problema em código
• 🔍 Atenção a casos extremos e condições de contorno
• 📝 Código claro e comentado para explicar seu processo de pensamento

🏆 Habilidades Aprendidas

Ao emergir vitorioso da Skywatch Spire, você ganhará:

• 💪 Confiança na aplicação de BFS para resolver problemas de caminho mais curto
• 🌐 Habilidade aprimorada para trabalhar com grades 2D e sistemas de coordenadas
• 🔄 Experiência no rastreamento eficiente de células visitadas para evitar ciclos
• 📚 Hábitos aprimorados de organização e documentação de código
• 🎖️ Apreciação do poder dos algoritmos baseados em fila no pathfinding
• 🔬 Capacidade de visualizar algoritmos passo a passo para melhor compreensão e depuração

⚔️ Resolvendo o Desafio

Vamos dividir nossa abordagem de pathfinding BFS:

🔍 Entendendo Breadth-First Search (BFS)

Pense no BFS como explorar um labirinto seguindo esta regra simples: “Verifique todos os caminhos que têm 1 passo de comprimento, depois todos os caminhos que têm 2 passos de comprimento, depois 3 passos de comprimento”, e assim por diante.

Imagine que você está na entrada de um labirinto com vários caminhos que se ramificam. Em vez de ir fundo por um caminho antes de tentar outros:

1. Primeiro, olhe para cada caminho que está exatamente a 1 passo de distância
2. Depois, examine cada caminho que está exatamente a 2 passos de distância
3. Continue esse padrão, explorando tudo que está a uma distância de 3, depois 4, e assim por diante

É por isso que chamamos de “breadth-first” (busca em largura) – você explora toda a “largura” de possibilidades em cada distância antes de ir mais fundo.

O verdadeiro poder do BFS é que se você está procurando algo, sempre o encontrará usando o caminho mais curto possível. Isso acontece porque você verifica sistematicamente todos os caminhos mais curtos antes de considerar quaisquer caminhos mais longos.

📥 Entendendo o input

O layout da torre é uma grade 2D, onde:

• 0 representa uma célula vazia segura 🟩
• 1 representa um sentinela que deve ser evitado 🟥
• ‘E’ marca a célula de saída 🚪
• Nossa posição inicial é sempre (0,0) 🏁

A grade é fornecida como uma lista 2D no estilo Python, como:

[
    [0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0, 'E']
]

🐍 Implementando BFS

Aqui está nosso código Python para encontrar o caminho seguro mais curto:

from collections import deque

def shortest_safe_path(grid):
    # Encontrar posição de saída
    exit_position = None
    rows = len(grid)
    cols = len(grid[0])
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 'E':
                exit_position = (i, j)
                break
        if exit_position:
            break
    
    # Se não houver saída, nenhum caminho possível
    if not exit_position:
        return -1
    
    # Definir direções de movimento possíveis
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Inicializar BFS
    queue = deque([(0, 0, 0)])  # (linha, coluna, distância)
    visited = set([(0, 0)])  # Rastrear células visitadas
    
    # BFS até a fila esvaziar ou a saída ser encontrada
    while queue:
        row, col, distance = queue.popleft()
        if (row, col) == exit_position:
            return distance  # Saída encontrada, retornar comprimento do caminho
        
        # Explorar quatro células adjacentes
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            # Verificar se a nova posição é válida
            if (0 <= new_row < rows and
                0 <= new_col < cols and
                (new_row, new_col) not in visited and
                grid[new_row][new_col] != 1):
                queue.append((new_row, new_col, distance + 1))
                visited.add((new_row, new_col))
    
    # Fila esgotada, nenhum caminho encontrado
    return -1

# Ler grade da entrada e executar pathfinding
input_text = input()
grid = eval(input_text)
result = shortest_safe_path(grid)
print(result)

Agora, vamos entender o código passo a passo:

from collections import deque

def shortest_safe_path(grid):

• Importamos a classe deque (fila de duas extremidades) do módulo collections, que fornece uma maneira eficiente de implementar a fila BFS.
• Definimos a função principal shortest_safe_path que recebe a grade como entrada.

# Encontrar posição de saída
    exit_position = None
    rows = len(grid)
    cols = len(grid[0])
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 'E':
                exit_position = (i, j)
                break
        if exit_position:
            break

• Inicializamos exit_position como None e obtemos o número de linhas e colunas da grade.
• Iteramos por cada célula da grade usando loops aninhados.
• Se encontrarmos a célula de saída marcada como ‘E’, armazenamos sua posição como uma tupla (i, j) em exit_position e saímos de ambos os loops.

# Se não houver saída, nenhum caminho possível
    if not exit_position:
        return -1

• Se exit_position ainda for None após o loop, significa que não há célula de saída na grade.
• Nesse caso, retornamos -1 para indicar que nenhum caminho é possível.

# Definir direções de movimento possíveis
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

• Definimos uma lista directions que contém quatro tuplas representando as possíveis direções de movimento: para cima, para a direita, para baixo e para a esquerda.
• Cada tupla (dr, dc) representa a mudança na linha e na coluna ao se mover naquela direção.

# Inicializar BFS
    queue = deque([(0, 0, 0)])  # (linha, coluna, distância)
    visited = set([(0, 0)])  # Rastrear células visitadas

• Inicializamos a fila BFS queue como um deque com uma única tupla (0, 0, 0), representando a posição inicial (0, 0) e uma distância de 0.
• Também inicializamos um conjunto visited para manter o controle das células que já visitamos, começando com a posição inicial (0, 0).

# BFS até a fila esvaziar ou a saída ser encontrada
    while queue:
        row, col, distance = queue.popleft()
        if (row, col) == exit_position:
            return distance  # Saída encontrada, retornar comprimento do caminho
        
        # Explorar quatro células adjacentes
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            # Verificar se a nova posição é válida
            if (0 <= new_row < rows and 
                0 <= new_col < cols and
                (new_row, new_col) not in visited and
                grid[new_row][new_col] != 1):
                queue.append((new_row, new_col, distance + 1))
                visited.add((new_row, new_col))

• Iniciamos o loop BFS, que continua até que a fila esteja vazia ou encontremos a saída.
• Em cada iteração, removemos o elemento mais à esquerda da fila usando queue.popleft(), que representa a célula atual que estamos processando.
• Se a célula atual corresponder à posição de saída, encontramos o caminho mais curto e retornamos a distância.
• Caso contrário, exploramos as quatro células adjacentes iterando sobre a lista directions.
• Para cada direção, calculamos a nova linha e coluna adicionando os valores correspondentes dr e dc à linha e coluna atuais.
• Verificamos se a nova posição é válida, garantindo que esteja dentro dos limites da grade, não tenha sido visitada antes e não seja um sentinela (valor 1).
• Se a nova posição for válida, a adicionamos à fila junto com a distância atualizada (incrementada em 1) e a marcamos como visitada adicionando-a ao conjunto visited.

# Fila esgotada, nenhum caminho encontrado
    return -1

• Se o loop BFS for concluído sem encontrar a saída, significa que a fila foi esgotada e não existe caminho.
• Nesse caso, retornamos -1 para indicar que não foi encontrado um caminho seguro.

# Read grid from input and run pathfinding  
input_text = input()
grid = eval(input_text)
result = shortest_safe_path(grid)
print(result)

• Lemos a grade como uma string a partir da entrada do usuário usando input().
• Convertemos a string de entrada em uma lista 2D usando eval() e armazenamos na variável grid.
• Chamamos a função shortest_safe_path com a grid como argumento e armazenamos o resultado na variável result.
• Por fim, imprimimos o result, que representa o comprimento do caminho seguro mais curto ou -1 se não existir um caminho.

🎉 Triunfo na Skywatch Spire e Além! 🏆

Parabéns, bravo aventureiro! 🌟 Sua determinação inabalável e habilidades de programação afiadas o levaram a conquistar a traiçoeira Skywatch Spire e superar os Clockwork Sentinels rebeldes. 💪 O poder do Breadth-First Search iluminou o caminho para a vitória, guiando você através das reviravoltas e curvas desta missão desafiadora. 🗺️✨

Enquanto você se mantém firme no topo da torre, a vista panorâmica de Eldoria se estende diante de você—um testemunho da incrível jornada que você empreendeu. 🌄 Este CTF não apenas testou suas habilidades técnicas, mas também o envolveu em uma narrativa cativante que deu vida ao mundo de Eldoria. 📜🗡️

Através do desafio do Clockwork Guardian, você aprimorou suas habilidades em travessia de grafos, pathfinding baseado em grade e design eficiente de algoritmos. 🧩 Mas mais do que isso, você experimentou a emoção de ser um herói em um reino fantástico, enfrentando inimigos formidáveis e emergindo triunfante. 🛡️🐉

Ao concluirmos este épico post do blog, não posso deixar de sentir uma sensação de realização.

🗺️ Pronto para Mais Aventuras?

Quer explorar mais writeups do Cyber Apocalypse 2025? Confira minhas outras soluções aqui!