Laboratório 11 - Encaixe 2d - Algoritmos e Programação de Computadores 2022 2

16/11/2022 09:55 Laboratorio 11 Encaixe 2D Jogos de encaixe proporcionam uma Otima atividade tanto para criangas como para adultos. As criangas, particularmente, sao bastante beneficiadas por essa atividade, pois esse tipo de jogo estimula o desenvolvimento de orientagao espacial. Diferentes modelos sdo desenvolvidos no mercado visando atrair o publico adulto e infantil. " pS j a _ _——— Uma grande empresa esta desenvolvento um novo jogo de encaixe 2D. O jogo é composto por diferentes tabuleiros e pecas, sendo que os tabuleiros e as pegas sao retangulares e formados por células. Cada célula pode estar preenchida ou vazia. Em cada partida do jogo, 0 objetivo consiste em selecionar aleatoriamente um tabuleiro e uma pega e realizar o maior numero possivel de encaixes da peca no tabuleiro. Uma pega encaixa em uma determinada posi¢do do tabuleiro quando todas as células preenchidas da pega estao alinhadas com células vazias do tabuleiro. Além disso, a pega deve ser encaixada sem ultrapassar as dimens6es (largura e altura) do tabuleiro. O jogo permite ainda que a pega seja rotacionada para a direita em 90, 180 e 270 graus. https://susy.ic.unicamp.br:9999/mc102/11/enunciado.html 1/5 16/11/2022 09:55 Laboratorio 11 O engenheiro de producdo da empresa possui a representagao computacional de todos os tabuleiros e pegas que sdo produzidos. Sabendo de sua habilidade com programacao, ele pediu sua ajuda para determinar a quantidade maxima de encaixes que uma determinada peca pode ter em um determinado tabuleiro. Os tabuleiros e pegas sao representados por meio de matrizes, sendo que cada célula da matriz possui 0 caractere x ou . ,indicando que a célula esta preenchida ou vazia, respectivamente. A seguir, temos um exemplo de um tabuleiro representado por uma matriz 5x6. ~XX.X., X....X X....X ~XXXX., X XX X X X A seguir, temos um exemplo de uma pega representada por uma matriz 3x3. X.. . XX . XX Perceba que So é possivel encaixar a pega original (sem rotaciona-la) no tabuleiro a partir da primeira linha e primeira coluna. Além disso, rotacionando a pega em 90° também é possivel encaixa-la a partir da primeira linha, tanto a partir da segunda coluna, quanto a partir da quarta. Ja rotacionando 180°, podemos encaixar a peca a partir da segunda linha e quarta coluna. Por fim, rotacionando 270°, podemos encaixar a pe¢a a partir da segunda linha e da primeira coluna. O seu programa recebera como entrada um numero inteiro T , que indicaa altura do tabuleiro, seguido por T linhas que representam o tabuleiro. Em seguida, seu programa recebera um numero inteiro P , que indica a altura da peca , seguido por P linhas que representam a pega. As células do tabuleiro e da peca estado separadas pelo caractere de espacgo " ".Vocé pode assumir que a altura e largura da pega sempre sera menor ou igual do que a altura e largura do tabuleiro. A saida do seu programa devera informar a quantidade de posicgdes no tabuleiro em que é€ possivel encaixar a pe¢a original e rotacionada para direita em 90°, 180° e 270°. Exemplos de entradas e saidas esperadas pelo seu programa: Teste 01 https://susy.ic.unicamp.br:9999/mc102/11/enunciado.html 2/5 16/11/2022 09:55 Laboratório 11 https://susy.ic.unicamp.br:9999/mc102/11/enunciado.html 3/5 Entrada 5 . X X . X . X . . . . X X . . . . X . X X X X . X X X X X X 3 X . . . X X . X X Saída 1,2,1,1 Teste 02 Entrada 7 X X X X X X X X X X X X X X X X X . X X X X X . . . X X X X X X X X X X X X X X X X X X X X X X X 2 X X X . Saída 0,0,1,1 Teste 03 Entrada 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16/11/2022 09:55 Laboratório 11 https://susy.ic.unicamp.br:9999/mc102/11/enunciado.html 4/5 . . . X . . . X . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . X . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . X . . . X 4 X X X X X X X X X X X X . X X X Saída 6,4,6,9 Código Base No arquivo auxiliar lab11.py você irá encontrar um código base para dar início ao processo de elaboração deste laboratório. Para facilitar a implementação do seu programa, o código base realiza a leitura do tabuleiro e da peça. # Leitura do tabuleiro T = int(input()) tabuleiro = [] for _ in range(T): tabuleiro.append(input().split()) # Leitura da peça P = int(input()) peca = [] for _ in range(P): peca.append(input().split()) Orientações Veja aqui a página de submissão da tarefa. O arquivo a ser submetido deve se chamar lab11.py. No link "Arquivos auxiliares" há um arquivo compactado (aux11.zip) que contém todos os arquivos de testes abertos (entradas e saídas esperadas). O laboratório é composto de 10 testes abertos e 10 testes fechados. 16/11/2022 09:55 Laboratorio 11 e Olimite maximo sera de 20 submiss6es. e Acesse 0 sistema SuSy com seu RA (apenas numeros) e a senha que vocé utiliza para fazer acesso ao sistema da DAC. e Vocé deve seguir as instrugdes de submissdo descritas no enunciado. e Serdo considerados apenas os resultados da ultima submissdo. e Esta tarefa tem peso 3. e Oprazo final para submissdo é dia 20/11/2022 (domingo). https://susy.ic.unicamp.br:9999/mc102/11/enunciado.html 5/5