Ruta más corta [2]

#!/usr/bin/python
# -*- coding: utf8 -*-
def camino_matriz(f1,c1,f2,c2,lista): #Creamos la función que nos dará la ruta más corta, incluyendo pasos diagonales y horizontales
    if (f1==f2):    #comparamos f1 y f2, en caso de ser cierta, solo nos desplazamos de forma horizontal
        if(c1==c2):
            lista[f1][c1]="+"
            print "Ruta Encontrada..."
        elif (c1<c2):
            lista[f1][c1]="+"
            camino_matriz(f1,c1+1,f2,c2,lista)      #Recursividad
        else:
            print "Error en la parte de columnas"
    elif (f1+1==f2):     #comparamos la fila siguiente con la final, si son iguales, solo es necesario un  movimiento en las columnas (horizontal o diagonal)
        if (c1==c2):
            lista[f1+1][c1]="+"
            print "Ruta Encontrada..."
        elif (c1+1==c2):
            lista[f1+1][c1+1]="+"
            print "Ruta Encontrada..."
        else :
            lista[f1+1][c1+1]="+"
            camino_matriz(f1+1,c1+1,f2,c2,lista)        #Recursividad
    elif (f1+1<f2):     #Comparamos la fila siguiente con la final, en caso de que la siguiente sea menor que la final, se hace un paso a (f1+1,c1+1)
        if (c1==c2):
            lista[f1+1][c1]="+"
            camino_matriz(f1+1,c1,f2,c2,lista)      #Recursividad
        elif (c1+1==c2):
            lista[f1+1][c1+1]="+"
            camino_matriz(f1+1,c1+1,f2,c2,lista)        #Recursividad
        else:
            lista[f1+1][c1+1]="+"
            camino_matriz(f1+1,c1+1,f2,c2,lista)
    else:
        print "..Error con los datos ingresados.."
    return lista

def matriz(M,N):    #Aquí creamos la matriz de un tamaño MxN designado por el usuario
    lista=[]
    for x in range(M):
        columnas=[]
        for y in range(N):
            columnas.append("x")
        lista.append(columnas)
    return lista

filas,columnas=input("Ingrese el tamaño de la matriz (filas,columnas), separando por con una coma (,) los valores: ")   #pedimos el tamaño de la matriz
generando_m=matriz(filas,columnas)  #Generamos la matriz

print "Generando una matriz de {0}x{1} ...".format(filas,columnas)
for x in range(filas):  #Por estetica, imprimimos las matrices por filas.
    print generando_m[x]

print ""
f_final,c_final=input("Ingrese las coordenadas del punto final P, separando por una coma (,), los valores: ")       #Pedimos las coordenadas del punto final
solucion=camino_matriz(0,0,f_final-1,c_final-1,generando_m) #Una vez obtenidas las coordenadas y generada la matriz, le pasamos los datos a nuestra función que nos dará la ruta más corta
print ""
print "Generando una Ruta desde el punto O(0,0) hasta el punto P({0},{1})".format(f_final,c_final)

for x in range(filas):  #Por estetica imprimimos el resultado de la ruta, por filas.
    print solucion[x]
input("")