# Last edited on 2018-04-03 18:03:08 by stolfilocal

def pega_tabuleiro():
  """Pede pro usuario digitar um tabuleiro retangular de letras.  
  Cada ENTER termina uma mova linha do tabuleiro. Todas as linhas 
  devem ter o mesmo comprimento. O usuario indica o fim do 
  tabuleiro por uma linha vazia.  A funcao devolve o 
  tabuleiro na forma de uma lista, onde cada elemento eh uma
  linha do tabuleiro, na forma de uma cadeia."""
  
  tab = [ ];  # O tabulairo.  Cada elemento eh uma lista com caracters de uma linha.
  while True:
    lin = input("? ")
    if (lin == ""):
      return tab
    tab = tab + [ lin ]

def verifica_pal_hor(pal, tab, i, j):
  """Determina se a palavra pal ocorre em posicoes consecutivas
  na linha i do tabuleiro tab, comecando na coluna j."""
  
  lins = len(tab) # Numero de linhas.
  cols = len(tab[0]) # Numero de colunas.
  n = len(pal) # Numero de letras na palavra.
  for k in range(n):
    # Testa a letra [k] de pal:
    if (j + k >= cols) or (pal[k] != tab[i][j+k]):
      return False
  return True
    
def verifica_pal_ver(pal, tab, i, j):
  """Determina se a palavra pal ocorre em posicoes consecutivas
  na coluna j do tabuleiro tab, comecando na linha i."""
  
  lins = len(tab) # Numero de linhas.
  cols = len(tab[0]) # Numero de colunas.
  n = len(pal) # Numero de letras na palavra.
  for k in range(n):
    # Testa a letra [k] de pal:
    if (i + k >= lins) or (pal[k] != tab[i+k][j]):
      return False
  return True
  
def procura_palavra_no_tab_hor(pal, tab):
  """Dada uma cadeia de letras pal e um tabuleiro de caracteres tab, procura 
  em tab a palavra pal em posicoes consecutivas na mesma linha.
  Se enontrar, devolve os indices da linha e coluna onde 
  a palavra comeca.  Se nao encontrar, devolve (-1,-1).""" 
  
  lins = len(tab) # Numero de linhas.
  cols = len(tab[0]) # Numero de colunas.
  for i in range(lins):
    for j in range(cols):
      if verifica_pal_hor(pal, tab, i, j):
        return (i,j)
  return (-1,-1)
    
def procura_palavra_no_tab_ver(pal, tab):
  """Dada uma cadeia de letras pal e um tabuleiro de caracteres tab, procura 
  em tab a palavra pal em posicoes consecutivas na mesma coluna.
  Se enontrar, devolve os indices da linha e coluna onde 
  a palavra comeca.  Se nao encontrar, devolve (-1,-1).""" 
  
  lins = len(tab) # Numero de linhas.
  cols = len(tab[0]) # Numero de colunas.
  for i in range(lins):
    for j in range(cols):
      if verifica_pal_ver(pal, tab, i, j):
        return (i,j)
  return (-1,-1)

tab = pega_tabuleiro()
pal = input("palavra a buscar? ")
print("")
(ih,jh) = procura_palavra_no_tab_hor(pal, tab)
(iv,jv) = procura_palavra_no_tab_ver(pal, tab)
if (ih >= 0) and (jh >= 0):
  print("Palavra encontrada na horizontal, comecando na linha %d e coluna %d." % (ih, jh))
elif (iv >= 0) and (jv >= 0):
  print("Palavra encontrada na vertical, comecando na linha %d e coluna %d." % (iv, jv))
else:
  print("Palavra nao encontrada.")