0647-o-gato-do-zelador-do-armaz

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.4" id: 647 name: O Gato do Zelador do Armazém slug: o-gato-do-zelador-do-armaz timeLimitSegs: 2.0 difficultyLevelId: D author: Gabriel Peixoto origin: Seletiva IME-USP 2014 description: | Nesta versão bérbere do Sokoban, você controla um gato que pode se movimentar em 4 direções e empurrar blocos de terra (nunca puxar). O objetivo é empurrar o bloco até uma posição final especificada 'x', abrindo o menor número possível de portas '#'. Sempre que o gato ocupa uma posição com porta pela primeira vez, a porta é aberta, comportando-se como posição livre daí em diante. O bloco não pode ser empurrado para uma porta fechada. Calcule o número mínimo de portas abertas e o número de movimentos necessários, ou imprima -1 se for impossível. editorial: | **Briefing para o Professor:** Problema avançado de grafos em grid com múltiplos estados simultâneos (Sokoban-like). Exige conhecimento de Busca em Grafos (Dijkstra ou BFS com restrições/pesos) com um estado expandido. A posição atual do personagem não é suficiente, é preciso armazenar a posição do bloco e as portas abertas (bitmask). **Estratégia de Resolução:** Estado do Dijkstra: `(cat_r, cat_c, block_r, block_c, portas_abertas)`. As arestas (transições) são: o gato andar para um espaço vazio, abrir uma porta, ou empurrar o bloco (se o gato e o bloco estiverem adjacentes e na mesma direção). O peso primordial da busca é a quantidade de portas abertas (d1), e o peso secundário é o número de passos do gato (d2). A prioridade na `PriorityQueue` reflete isso. Complexidade: $O(N^2 M^2 2^P \log(\dots))$. Para detalhes, consulte o nível D. successmsg: 'Miau! Você guiou o gato pelas portas bérberes com o mínimo esforço possível!' timeComplexity: O(N^2 M^2 2^P \log X) skills: - graphs - dijkstra - bitmask statements: - id: a-o-gato-do-zelador-do-armaz testScenarioLevel: A thematicSkills: - skill: history points: 1 testScenarios: - id: a-performance name: Mapas Gigantes (até 25x25) com Portas description: "Mapas que atingem os limites do estado (N=25, M=25, P=5)." helpTip: "Sua fila de prioridade lida com estados bitmask corretamente sem exceder a memória?" level: A testType: PERFORMANCE skills: - skill: graphs points: 1 - id: b-edge-cases name: Casos Limites description: "Caminhos bloqueados (impossíveis, resposta -1), mapas mínimos 2x2." helpTip: "Retorne -1 adequadamente caso a fila esvazie sem encontrar a solução." level: B testType: TDD skills: - skill: dijkstra points: 1 - id: c-basic name: Mapas Básicos sem Portas description: "Sokoban tradicional em mapas 3x4 a 6x6." helpTip: "Verifique a movimentação clássica do Sokoban (apenas empurrar)." level: C testType: TDD skills: - skill: graphs points: 1 - id: d-sample name: Exemplo do Enunciado description: "Exemplos do PDF original." helpTip: "Passe nos três exemplos providos." level: D testType: TDD skills: - skill: dijkstra points: 1 solutions: [] authorSlugProblem: Unknown defaultStatement: a-o-gato-do-zelador-do-armaz