0510-toca-do-saci

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 510 name: "Toca do Saci" origin: "obi-2016" slug: "toca-do-saci" authorSlugEditorial: "alessio" authorSlugProblem: "desconhecido" description: "Dada uma matriz que representa uma toca, encontre o comprimento do caminho único entre a posição inicial e a saída." editorial: "O problema pede o tamanho do caminho entre a posição 3 (saída) e a posição 2 (Emília). Como o enunciado garante que a Emília não passou pela mesma sala mais de uma vez e não há ambiguidades, o caminho é uma linha única sem ramificações. Assim, podemos iniciar as coordenadas na posição 3 e percorrer a matriz iterativamente verificando as 4 direções ortogonais (usando os arrays `dx` e `dy`). Para cada passo, substituímos o valor atual por 0 para destruir o caminho de volta (evitando loops), e avançamos para a próxima célula que tiver valor > 0. O loop encerra quando alcançamos a posição 2. Adicionar uma borda de zeros (padding) ao redor da matriz principal no momento da alocação é um excelente truque para dispensar verificações explícitas de limites (out of bounds) em cada passo da simulação." successmsg: "Caminho perfeitamente rastreado! Você utilizou vetores de direção para iterar no trajeto e protegeu a matriz com bordas de forma exímia, escapando de Segment Faults indesejados." difficultyLevelId: C timeComplexity: "O(N \\times M)" spaceComplexity: "O(N \\times M)" timeLimitSegs: 1.0 memoryLimitMb: 128 defaultStatement: "a_pt_0510-toca-do-saci" skills: - "io" - "matrizes" - "loops" - "vetores-direcao" statements: - id: "a-0510-toca-do-saci" testScenarioLevel: A thematicSkills: - points: 2 skill: "mitologia-folclore" testScenarios: - id: "d-sample" name: "Amostras da OBI" description: "Casos de exemplos básicos do enunciado, cobrindo finais de corredores e o caso limítrofe onde a Emília começa no meio do trajeto." helpTip: "Você considerou o que acontece quando a Emília está no meio do corredor? O algoritmo caminha para os dois lados ou consegue ir apenas na direção correta do 2?" level: D testType: TDD skills: - points: 1 skill: "io" - id: "main" name: "Labirintos Completos" description: "Testes massivos, com matrizes de até 1000x1000 com corredores sinuosos." helpTip: "Sua matriz pode suportar a busca nas bordas limítrofes do grid 1000x1000 sem estourar limites de memória (Out Of Bounds)? Recomendamos aplicar padding (tamanho N+2, M+2)." level: C testType: TDD skills: - points: 2 skill: "matrizes" - points: 2 skill: "vetores-direcao" - id: "c-fuzzing" name: "Fuzzing de Percurso" description: "Caminhos aleatórios simulados." helpTip: "O código funciona para matrizes com caminhos complexos que não seguem uma estrutura simples em 'S' ou caracol?" level: C testType: INPUT skills: - points: 1 skill: "loops" - points: 1 skill: "vetores-direcao" - id: "b-limites" name: "Casos Extremos (Pequenos e Bordas)" description: "Matriz 1x2 ou caminhos que esbarram nas extremidades da matriz." helpTip: "Você tem verificação de borda (out of bounds) eficiente? Arrays de tamanho extra (padding) evitam erros na leitura dos limites (x=0, y=M)." level: B testType: TDD skills: - points: 1 skill: "matrizes" - points: 1 skill: "condicionais" - id: "a-performance-load" name: "Labirinto Massivo (N,M=1000)" description: "Matriz colossal de 1000x1000 preenchida por um único caminho extremamente longo simulando o pior caso." helpTip: "Buscas exaustivas ou recursão profunda estourarão a memória ou o tempo aqui. Simulação linear iterativa é a solução O(N*M)." level: A testType: PERFORMANCE skills: - points: 2 skill: "matrizes" - points: 2 skill: "complexity-analysis" solutions: - id: "a-otima-basica" name: "Simulação Linear com Padding" description: "Simulação O(N x M) iterativa, a partir da saída e destruindo o caminho. Incorpora padding de +2 posições na matriz." level: A implementations: - filenames: - solution.py language: py paradigm: Imperative - filenames: - solution.cpp language: cpp paradigm: Imperative - filenames: - Solution.java language: java paradigm: Imperative