Jogo das Bandeiras - Solucao com Busca em Profundidade Iterativa

Bandeira Juscelino resolveu ajudar seu filho Juscelino Jr a desenvolver algumas habilidades em lógica Para isso ele criou o seguinte jogo em um tabuleiro de N linhas e M colunas ele dispôs soldadinhos com diferentes bandeiras De forma que cada casa do tabuleiro tenha exatamente um soldado Um soldado x pode converter um soldado y que esteja em uma das casas adjacentes a ele ou seja se y estiver acima abaixo à esquerda ou à direita de x O jogador deve escolher uma bandeira para a casa na posição 00 de forma que a bandeira escolhida seja diferente daquela carregada pelo soldado nesta casa Sejam k a bandeira inicial da casa 00 e w a bandeira escolhida pelo jogador A partir da troca da bandeira k pela bandeira w da casa 00 os soldados adjacentes ao soldado desta casa que tiverem a bandeira k serão convertidos para a bandeira w Em seguida os soldados adjacentes a estes últimos que tiverem a bandeira k serão convertidos para a bandeira w e assim sucessivamente até que não haja mais soldados adjacentes aos últimos convertidos que tenham a bandeira k O objetivo do jogo é converter todos os soldados do tabuleiro para uma mesma bandeira com o número mínimo de troca de bandeiras para o soldado na casa 00 Escreva um programa que utiliza a busca em profundidade iterativa para alcançar o objetivo do jogo para qualquer instância criado por Juscelino Entrada A primeira linha de entrada tem dois inteiros N e M 1 NM 400 o número de linhas e colunas do tabuleiro A próxima linha conterá um número B 1 B 100 o número de bandeiras distintas que o tabuleiro pode ter inicialmente Depois disso há N linhas com M inteiros separados por espaço Cada inteiro terá um valor entre 0 e B 1 inclusive estes dois valores representando a bandeira da casa Saída Imprima na primeira linha o número mínimo de trocas de bandeiras da casa 00 necessário para alcançar o objetivo do jogo Na segunda linha imprima a sequência de bandeiras atribuídas à casa 00 pelo jogador valores numéricos para alcançar o objetivo Exemplo de Entrada Exemplo de Saída 4 4 2 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0 2 1 0 1 Observações Caso não seja implementado a busca em profundidade iterativa o trabalho receberá nota zero Não será aceita a versão recursiva da busca Caso o programa não encontre o número mínimo de trocas de bandeiras na posição 00 do tabuleiro objetivo do jogo a nota do trabalho será zero O formato de entrada e de saída devem ser obedecidos Caso contrário a nota do trabalho será zero Isso significa que O programa não deve imprimir nenhuma mensagem para solicitar qualquer dado O programa não deve imprimir nada além do que está descrito na Seção Saída 2 Relatório e Entrega do trabalho Além dos códigos fontes deve ser entregue um relatório com a documentação do trabalho onde deverão constar A apresentação de todas as estruturas implementadas e a relação entre tais estruturas no trabalho A descrição de cada função implementada divididas em trechos de códigos ou apresentada integralmente com a explicação de cada caso analisado A explicação sobre a organização dos arquivos criados pelo programa A descrição do arquivo makefile EXERCÍCIO DA BANDEIRA PYTHON def convertersoldadostabuleiro N M B def ehvalidoi j Verifica se as coordenadas i j estão dentro dos limites do tabuleiro return i 0 and i N and j 0 and j M def obtersoldadosadjacentesi j soldado Obtém as coordenadas dos soldados adjacentes à posição i j que possuem o mesmo valor de soldado soldadosadjacentes if ehvalidoi1 j and tabuleiroi1j soldado soldadosadjacentesappendi1 j if ehvalidoi1 j and tabuleiroi1j soldado soldadosadjacentesappendi1 j if ehvalidoi j1 and tabuleiroij1 soldado soldadosadjacentesappendi j1 if ehvalidoi j1 and tabuleiroij1 soldado soldadosadjacentesappendi j1 return soldadosadjacentes def dfsi j soldado Executa uma busca em profundidade DFS a partir da posição i j para alterar os soldados pilha i j while pilha x y pilhapop tabuleiroxy novosoldado soldadosadjacentes obtersoldadosadjacentesx y soldado for adjacente in soldadosadjacentes pilhaappendadjacente soldadoinicial tabuleiro00 novosoldado soldadoinicial 1 B count 0 sequencia soldadoinicial for i in rangeN for j in rangeM if tabuleiroij soldadoinicial Para cada soldado inicial encontrado executa uma busca em profundidade DFS para alterar os soldados adjacentes dfsi j soldadoinicial count 1 sequenciaappendnovosoldado dfs0 0 soldadoinicial return count 2 sequencia EXERCÍCIO DA BANDEIRA PYTHON Leitura da entrada N M mapint inputsplit B intinput tabuleiro for in rangeN linha listmapint inputsplit tabuleiroappendlinha Chamada da função mintrocas sequenciatroca convertersoldadostabuleiro N M B Inverter a sequência sequenciatroca sequenciatrocareverse Impressão da saída printmintrocas print joinstrtroca for troca in sequenciatroca BREVE EXPLICAÇÃO O código fornecido implementa uma função chamada convertersoldados que realiza uma transformação em um tabuleiro de soldados representado por uma matriz O objetivo é agrupar os soldados adjacentes que possuem o mesmo valor e substituílos por um novo valor calculado a partir de uma operação modular A função utiliza uma busca em profundidade DFS para percorrer o tabuleiro e encontrar grupos de soldados com o mesmo valor Cada grupo é substituído pelo novo valor calculado O número de transformações realizadas é contabilizado Após a execução da função o programa lê a entrada do usuário para obter as dimensões do tabuleiro o valor de referência e os valores dos soldados Em seguida a função convertersoldados é chamada com os parâmetros apropriados O resultado da transformação é armazenado nas variáveis mintrocas e sequenciatroca Para finalizar a sequência de transformações é invertida e a saída é exibida na tela apresentando o número mínimo de trocas realizadas e a sequência de transformações efetuadas no tabuleiro de soldados EXEMPLO DE ENTRADA E SAÍDA NO TERMINAL