QUADRADO - Construtores de Totens
Várias civilizações pré-colombianas habitaram a região de Alberta, Canadá. Pouco restou destas culturas, dizimadas pelo frio intenso, pelos ursos e, finalmente, pelos invasores ingleses e franceses que chegaram depois do descobrimento. Hoje, pesquisadores da Universidade de Alberta tentam desvendar os mistérios destes povos, estudando os totens produzidos na região.
Estudos do departamento de artes da universidade mostraram que os
construtores de totens gostavam de marcá-los com várias cópias de suas
assinaturas. A assinatura do artista era feita com sulcos verticais
"|
" e horizontais "_
".
Estudiosos imaginam que o símbolo era uma representação do mal na
cultura primitiva, e portanto, tabu) construindo um padrão quadrado.
Já foram identificadas várias assinaturas de artistas daquela época.
Sua tarefa neste problema é fazer um programa que recebe o desenho de
um totem, através de um padrão quadrado de tamanho n x n
de
sulcos verticais e horizontais, e uma assinatura quadrada de tamanho
m x m
com um padrão do mesmo tipo e encontra todas as
ocorrências da assinatura no totem.
Entrada
A entrada é composta de diversas instâncias. A primeira linha de cada
instância consiste em dois inteiros n
(1 <= n <= 1000
) e m
(1 <= m <= 60
e m < n
), indicando os tamanhos dos quadrados.
Nas n
linhas seguintes temos n
caracteres "|
" ou
"_
" que representam os caracteres do quadrado n x
n
. Nas m
linhas seguintes temos m
caracteres "|
" ou
"_
" que representam os caracteres do quadrado m x
m
.
A entrada termina com final de arquivo.
Saída
Para cada instância, você deverá imprimir um identificador
Instancia k
, onde k
é o número da instância atual. Imprima
a lista de todas ocorrências linha coluna
(o canto superior
esquerdo é a posição 0 0
) do quadrado m x m
no
quadrado n x n
. A saída deve estar ordenada primeiro pelas
colunas e em seguida pelas linhas. Caso não tenha nenhuma ocorrência
imprima uma linha com nenhuma ocorrencia
.
Após cada instância imprima uma linha em branco.
Exemplo
Entrada: 4 2 _|__ ___| __|_ ||__ _| |_ Saída: Instancia 1 2 1 1 2
Added by: | Wanderley Guimarăes |
Date: | 2007-08-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Seletiva para Maratona de Programação do IME - 2007 |