# Last edited on 2018-04-03 18:12:53 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(pal, tab, i, j, di, dj):
  """Determina se a palavra pal ocorre em posicoes consecutivas
  do tabuleiro tab, comecando na linha i e coluna j, e prosseguindo
  na direcao (di,dj).   Cada parametro di ou dj pode ser -1, 0, ou +1."""
  
  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:
    ii = i + k*di
    jj = j + k*dj
    if (ii < 0) or (ii >= lins) or (jj < 0) or (jj >= cols) or (pal[k] != tab[ii][jj]):
      return False
  return True
 
def procura_palavra_no_tab(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 i, j da linha e coluna onde 
  a palavra comeca, e a direcao di, dj da palavra no tabuleiro.  
  Se nao encontrar, devolve (-1,-1,-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):
      for di in [-1, 0, +1]:
        for dj in [-1, 0, +1]:
          if verifica_pal(pal, tab, i, j, di, dj):
            return (i,j,di,dj)
  return (-1,-1,-1,-1)

tab = pega_tabuleiro()
pal = input("palavra a buscar? ")
print("")
(i,j,di,dj) = procura_palavra_no_tab(pal, tab)
if (i >= 0) and (j >= 0):
  print("Palavra encontrada comecando na linha %d e coluna %d na direcao %+d,%+d." % (i, j, di, dj))
else:
  print("Palavra nao encontrada.")