Python: cómo encontrar una manera y visitar todas las celdas

Cerrado. Esta pregunta necesita detalles o claridad. Actualmente no acepta respuestas.

¿Quieres mejorar esta pregunta? Añade detalles y aclara el problema editando esta publicación.

Cerrado

hace 2 años

.

mejorar esta pregunta

¿Cómo puedo pasar esta tarea en Python? Según tengo entendido, necesito hacer algo con Matrix, pero ¿cómo forzar exactamente al programa a encontrar el camino? Necesito comenzar desde el punto 1 y terminar en el 2 y visitar cada uno solo una vez.

Busque algoritmos de búsqueda de rutas. Hay muchos de ellos y hay mucha información para leer antes de comenzar cualquier implementación.

-OscuridadPlusPlus

28/03/2021 a las 14:55

------------------------------------

Creo que DFS puede resolver tu problema.

------------------------------------

Resuelto en este momento, gracias por todo

import matplotlib.pyplot as plt

S, F, W, X = 1, 2, 0, None
FIELD = [[X,S,W,W,W,W],
         [W,W,W,W,W,W],
         [W,W,W,W,W,W],
         [W,W,W,W,W,F],
         [W,W,W,X,W,W],
         [W,W,W,W,W,W]]
ROWS = len(FIELD)
COLS = len(FIELD[0])

START_POS  = [(i, line.index(S)) for i, line in enumerate(FIELD) if S in line][0]
FINISH_POS = [(i, line.index(F)) for i, line in enumerate(FIELD) if F in line][0]
STEPS      = sum(line.count(W) for line in FIELD) + 1

print("Start:", START_POS, "\nFinish:", FINISH_POS, "\nTotal steps:", STEPS)

def do_step(level, path, points):
    global FIELD
    r, c = points[-1]   
    if r<0 or c<0 or r>=ROWS or c>=COLS or FIELD[r][c] == X:
        return
    if level == STEPS and (r, c) == FINISH_POS:
        print("Found path:", path) 
        yy, xx = zip(*points)
        plt.plot(xx, yy, "-ok")
        plt.gca().invert_yaxis()
        plt.show()
        exit()

    current = FIELD[r][c] 
    FIELD[r][c] = X      
    for dr, dc, dir in ((-1,0,'^'), (0,1,'>'), (1,0,'v'), (0,-1,'<')):
        do_step(level+1, path+dir, points+[(r+dr,c+dc)])
    FIELD[r][c] = current 
do_step(0, "", [START_POS])
print("No path's found.")