1404-megadamas

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 1404 name: "MegaDamas" slug: "megadamas" author: "Ricardo Anido, Brazil" origin: "Beecrowd 1404" timelimit: 1.0 memlimit: 200 difficultyLevelId: D description: "Simulação de tabuleiro de jogo de damas para encontrar a maior cadeia de capturas usando Backtracking/DFS." editorial: | Para resolver esse problema, devemos primeiro mapear o array 1D de casas para uma grade 2D (N x M). Sabendo que as casas escuras estão nas posições onde (linha + coluna) % 2 == 0, a reconstrução é direta. Para achar a maior cadeia de capturas, iteramos sobre todas as nossas peças (valor 1) e iniciamos uma Busca em Profundidade (DFS) para cada uma. Durante a DFS, simulamos os saltos nas 4 direções diagonais: se a casa adjacente tem o oponente (2) e a próxima (o destino do salto) está vazia (0), efetuamos a captura. No código, isso se traduz em transformar o oponente em 0 temporariamente (Backtracking), chamar a recursão, e depois devolver o oponente para a casa, maximizando o resultado em cada ramificação! successmsg: "Magistral! Você demonstrou domínio profundo em modelagem de tabuleiros (Matrizes) e exploração de estados com DFS e Backtracking!" timeComplexity: O(P \cdot 4^K) skills: - backtracking - matrix - dfs statements: - id: a-megadamas testScenarioLevel: A thematicSkills: - skill: matrix points: 1 - skill: backtracking points: 2 testScenarios: - id: a-performance name: Tabuleiros Cheios description: "Tabuleiros 20x20 com dezenas de ramificações." helpTip: "Backtracking limpo rodará instantaneamente devido à limitação geométrica de saltos." level: A testType: PERFORMANCE skills: - skill: backtracking points: 1 - id: b-fuzzing name: Capturas Variadas description: "Casos variados de capturas múltiplas." helpTip: "Você reseta o tabuleiro perfeitamente após simular a DFS de uma peça?" level: B testType: TDD skills: - skill: dfs points: 1 - id: c-edge name: Sem Oponentes ou Travado description: "Casos sem movimento possível." helpTip: "O que ocorre se o tabuleiro inteiro for de peças suas?" level: C testType: TDD skills: - skill: logic points: 1 - id: d-sample name: Exemplo description: "Casos base do problema." helpTip: "Passe." level: D testType: TDD skills: - skill: logic points: 1 solutions: - id: a-otima-basica name: DFS e Backtracking no Tabuleiro description: Algoritmo mapeando 1D para 2D e explorando saltos recursivos. level: A implementations: - language: cpp paradigm: Imperative main: megadamas.cpp filenames: - megadamas.cpp - language: py paradigm: Imperative main: megadamas.py filenames: - megadamas.py - language: java paradigm: OO main: Megadamas filenames: - Megadamas.java authorSlugProblem: Unknown defaultStatement: a-megadamas