Labirinto Formiga

labirinto = '''
+-----+-----+-+
|     |     | |
| | +-+  -+ | |
| | |     | | |
| |E  +---+ | S
| | | |     | |
|   | | | | | |
|-----+ +-+-+ |
|     | | |   |
| +-+   | |  -|
| |-+-|   |-  |
| | | +---+-- |
|             |
+-------------+
'''

ENTRADA, LIVRE, VISITADO, SOLUÇÃO, SAÍDA = 'E .oS'
def saiu(x, y):
    if lab[x][y] == SAÍDA:
        return True
    elif lab[x][y] == ENTRADA or lab[x][y] == LIVRE:
        lab[x][y] = VISITADO
        if saiu(x-1, y) or saiu(x+1, y) or \
           saiu(x, y-1) or saiu(x, y+1):
            lab[x][y] = SOLUÇÃO
            return True
    else:
        return False

lab = [list(linha)
       for linha in labirinto.splitlines() if linha]
x = [row.count(ENTRADA) for row in lab].index(1)
y = lab[x].index(ENTRADA)
if saiu(x, y):
    print ('\n'.join(''.join(linha) for linha in lab))
else:
    print ('A formiga irá morrer...')