python与矩阵探路（DFS）的麻烦

Question

我对DFS遇到问题，可能是在面对墙时来自递归中的问题。

它不是不断地进行只能导致墙壁的尝试，而应返回其先前的位置并尝试另一条路径。

，它严重依靠尝试的尝试（N，S，E，W或其他组合）

此外

def portal(M,l,c):  # locates current portal and changes position (if entering portal 1, go to portal 2)
    for elem in D.keys():
        x = 1
        if elem == M[l][c]:
            if [l,c] == D[elem][0] and x: [l,c] = D[elem][1]; x -=1
            if [l,c] == D[elem][1] and x: [l,c] = D[elem][0]; x-=1
    return [l,c]
    
def dfs(Q,p):
    l, c = Q[-1]     # previous position
    if [l,c] == COORD: return True
    for dir in [(l-1, c,1), (l, c - 1,2), (l , c+1,3), (l+1 ,c,4)]:    # dir = (l,c,p) = next row, next column and a number that represents the direction taken (1 = north)
        j=1
        if p:
            if dir[2] == p:         # if passing through a portal, p should not update, or else it would attempt to move in a direction it's not intended to
                nextl,nextc = dir[:2]
                print(nextl,nextc,l,c)
            else:  j = 0           # p is not 0 and no move happens (j = 0)
        else:                      # if no portal has been used: try all possible directions
            nextl, nextc, p = dir
        if j:
            if len(M[0]) > c >= 0 and 0 <= l < len(M):    # if inbounds
                if M[nextl][nextc] in D:                  # if the next move lands in a portal, change coordinates using the function portal()
                    Q.append((nextl,nextc))
                    nextl,nextc = portal(M,nextl,nextc)
                if M[nextl][nextc] and ((nextl, nextc) not in Q) and (M[nextl][nextc] not in D):
                # if there is no wall on the next position and it has not been visited yet, call dfs again for the next position  
                    Q.append((nextl, nextc))
                    if dfs(Q,0):
                        return True
                    else:
                        Q.pop()
                elif M[nextl][nextc] and (M[nextl][nextc] in D) and ((nextl, nextc) not in Q):
               # if a portal has been used, the next move should keep previous p (direction). Therefore, the function call is different, to prevent it from attempting to move in all 4 directions.
                    Q.append((nextl,nextc))
                    if dfs(Q,p):
                        return True
                    else:
                        Q.pop()
                elif M[l][c] not in D: p = 0
             # resets p if no move is possible ( allows it to gain a new direction from the for loop above)
            else: p = 0
            
M = [];L = int(input())
for _ in range(L): M.append(input().split())     # Matrix input
for i in M:
    for h in i:
        if h == "#": M[M.index(i)][i.index(h)] = 0
        elif h == ".": M[M.index(i)][i.index(h)] = 1   # Replaces path with 1 (easier to write)

l0, c0 = (int(i) for i in input().split())
queue = [(l0, c0)]       # initial position

COORD = 0
D={};lineP=-1
for LINE in M:          # locates portals and assigns to the corresponding letter both coordinates
    colP = -1; lineP+=1
    for COL in LINE:
        colP+=1
        if COL not in ["*",0,1]:
            if COL in D: D[COL].append([lineP,colP])
            else: D[COL] = [[lineP,colP]]
        if COL == "*": COORD=[lineP,colP]    # locates the destination (marked with "*")

if dfs(queue,0):
    print("Success"
else:
    print("Failure")

Answer 1

我创建了一个可以找到可以达到目标的路径的脚本。如果路径不存在，它将打印任务是不可能的。

注意：该算法并未寻求所有可能的路径。一旦找到一个，它就会返回那条路。因此，它不会将最短的目标返回目标。如果存在，它将返回一条路径。否则，它将返回一个空列表。

dfs_pathfinder的返回是布尔值，说明是否找到了路径。要检索路径，请将列表存储到路径，然后通过参考将列表填充为参数。

我试图使用注释来解释脚本的每一行。如果您不了解某些内容或从中得到意外的错误，请随时将其发布在此答案的评论中。

# Swap rows by columns of a grid.
#
# Useful for printing on terminal only. Or, if you
# need to transpose the input grid.
def transpose(grid):
    tgrid = []

    ncols = range(len(grid[0]))
    nrows = range(len(grid))

    for j in ncols:
        tgrid.append([])
        for i in nrows:
            tgrid[-1].append(grid[i][j])

    return tgrid

# Handles the file input, loading:
# 1. The Character's starting position
# 2. The Grid itself
# 3. The Goal you want to reach 
# 4. The List of Portals
def handle_input(filename):
    portals = {}
    goal = (-1, -1)
    
    # Try to open the file and read all its lines
    try:
        file = open(filename, 'rt')
    except:
        print('Error: Couldn\'t open ' + filename)
    else:
        lines = file.readlines()
        file.close()

    # Get the number of rows
    nrows = int(lines[0][:-1])

    # Mount the grid based on the file data
    # Append all portals
    # Find the goal's position
    grid = []
    for nr in range(nrows):
        row = lines[nr+1][:-1].split(' ')

        for co in range(len(row)):
            if (row[co] != '.' and row[co] != '#' and row[co] != '*'):
                if (row[co] in portals):
                    if (len(portals[row[co]]) == 2):
                        print("Warning: There are 3 portals of same kind: ", row[co])

                    portals[row[co]].append((nr, co))
                else:
                    portals[row[co]] = [(nr, co)]
            elif (row[co] == '*'):
                goal = (nr, co)

        grid.append(row)

    # Retrieve the starting position
    pos = lines[nrows+1][:-1].split(' ')
    pos = (int(pos[0]), int(pos[1]))

    # Check if the goal exists
    if (goal[0] == -1 or goal[1] == -1):
        print('Warning: No goal * is set')

    return grid, pos, goal, portals

# Eases the way of retrieving the current tile character from the grid, given
# a position pos: (x, y)
#
# If a position outside of the grid is requested, return an empty character.
def get(grid, pos):
    if (pos[0] >= 0 and pos[1] >= 0 and pos[0] < len(grid) and pos[1] < len(grid[pos[0]])):
        return grid[pos[0]][pos[1]]
    else:
        return ''

# Each portal is a pair of positions: [(a, b), (c, d)]
#
# This means that portal1 is at (a, b)
# and portal2 is at (c, d)
#
# Calling enterPortal(portal, (a, b)) -> (c, d)
# Calling enterPortal(portal, (c, d)) -> (a, b)
def enterPortal(portal, pos):
    if (portal[0][0] == pos[0] and portal[0][1] == pos[1]):
        return portal[1]
    else:
        return portal[0]

# This function does not measures the best path. Nor, it searches all
# possible paths available to goal.
#
# It returns the first path to goal that is found. Otherwise, an empty
# path is returned, signalizing that the goal is unreachable.
def dfs_pathfinder(grid, pos, goal, portals, path, reached):
    char = get(grid, pos)
    reached.append(pos)

    # Still walking
    if (char == '.'):
        # Store all movement choices
        movement = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        # Try all movement choices
        for mv in movement:
            # Get a hint of next position
            nextPos = (pos[0] + mv[0], pos[1] + mv[1])

            # If the next position is not reached yet, continue
            if (nextPos not in reached):

                # Append current position to path
                path.append(pos)

                # And check if you are in the correct path
                if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
                    # If you reached goal, signalize to other levels of recursion
                    # that you found it.
                    return True
                else:
                    # If you're not, pop current position from path and try again
                    path.pop()

        # Didn't found goal. Giving up.
        return False

    # Steped on portal
    elif (char in portals):
        # Portals are unreachable. They teleport the character.
        #
        # However, we do append their position into path list.
        reached.pop()

        # Get the other end of the current portal
        other = enterPortal(portals[char], pos)

        # Get previous position, which will be used to calculate
        # which direction the character should face when stepping
        # outside of the portal exit
        prev = path[-1]
        
        # Check which position you came from
        diff = (prev[0] - pos[0], prev[1] - pos[1])

        # Get position you will face when exiting the portal
        # @ -> P ... O -> .
        # . <- O ... P <- @
        move = (-diff[0], -diff[1])

        # Calculate a hint of next position on other side of the portal
        nextPos = (other[0] + move[0], other[1] + move[1])

        # If the hint position is not reached yet:
        if (nextPos not in reached):
            path.append(pos)   # Stepped on portal
            path.append(other) # Stepped on other side of portal

            # Check if you're on the correct path to goal
            if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
                # You are. Signalize to other levels of recursion that you
                # found the goal.
                return True
            else:
                path.pop() # pop other side of portal
                path.pop() # pop current portal
                # You're wrong. Try again.

        # Didn't found goal. Giving Up.
        return False

    # Reached goal
    elif (char == '*'):
        path.append(pos) # Append goal to path.

        # Signalize to other levels of recursion that you found goal.
        return True

    # Cannot reach goal anymore. You are on a non-walkable tile.
    else:
        # Giving Up.
        return False

if __name__ == '__main__':
    # Step 1: Extract data
    grid, pos, goal, portals = handle_input('file.txt')

    # Step 2: Call Pathfinder
    path = []
    if (dfs_pathfinder(grid, pos, goal, portals, path, [])):
        print("A Path was found: ", path)
    else:
        print("No Path was found. Task is impossible.")

    # Step 3: Show the path inside the grid using counters
    k = 0
    for pos in path:
        grid[pos[0]][pos[1]] = str(k)
        k += 1

    # Step 4: Print the grid and the path the character must
    # go through to reach the goal
    print()
    grid = transpose(grid)
    gout = ''
    for j in range(len(grid[0])):
        for i in range(len(grid)):
            gout += ((' ' + get(grid, (i, j)) + '  ') if (len(get(grid, (i, j))) == 1) else (' ' + get(grid, (i, j)) + ' '))
        gout += '\n'
    print('The Grid: ')
    print(gout)
    print()

该脚本从文件中获取输入。在这种情况下，file.txt，其中的内容是：

7
# # * # # # # # #
. . . . T . . . .
# # # # # # # # .
. . . T . . . . .
Q . . . . # # # #
. . . . . Q . . .
. . . # # # . . .
5 1

测试脚本后，我得到了此输出：

A Path was found:  [(5, 1), (4, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (4, 3), (4, 4), (3, 4), (3, 3), (1, 4), (1, 3), (1, 2), (0, 2)]

The Grid:
 #   #   14  #   #   #   #   #   #
 .   .   13  12  11  .   .   .   .
 #   #   #   #   #   #   #   #   .
 .   2   3   10  9   .   .   .   .
 Q   1   4   7   8   #   #   #   #
 .   0   5   6   .   Q   .   .   .
 .   .   .   #   #   #   .   .   .

启动位置为0位置，14 < /代码>是目标。图块10和11都是门户网站t的两端，它告诉算法使用门户网站t要达到目标。