Jogo das Bandeiras - Solução 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 N M 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 2 1 0 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 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 Todas as implementações deverão ser desenvolvidas em grupo de até quatro alunos e deverá ser entregue até o dia 02072023 às 2355 hs no sistema AVA httpsavaufesbr Todos os arquivos devem ser compactados em um arquivo zip O nome do arquivo deve seguir o seguinte formato GrupoXnomedoaluno1nomedoaluno2nomedoaluno3nomedoaluno 4zip Onde X deve ser substituído pelo número do grupo 3 Avaliação do trabalho A apresentação do trabalho será realizado nos dias 03 e 04072023 nos horários e locais das aulas A ordem de apresentação dos grupos será definida por sorteio Todos os membros do grupo devem participar da apresentação Caso algum membro não participe da apresentação o grupo perderá pontos