在Python中进行对角线的首次搜索移动

我正在尝试编写程序以在迷宫中找到最短路径,但不能对角移动。

import queue 
def createMaze2():
    maze = []
    maze.append(["S", "X", "R", "X", "X"])
    maze.append(["R", "G", "X", "X", "R"])
    maze.append(["R", "R", "X", "X", "R"])
    maze.append(["X", "R", "X", "X", "R"])
    maze.append(["R", "R", "R", "R", "R"])

    return maze

def printMaze(maze, path=""):
    for x, pos in enumerate(maze[0]):
        if pos == "S":
            start = x

    i = start
    j = 0
    pos = set()
    for move in path:
        if move == "ul":
            if (j-1 == "X"):

                i -= 1
                j -= 1
            else:
                j -= 1
                i -= 1

        elif move == "ur":
            if(j-1=="X"):
                i += 1
                j -= 1
            else:
                j -= 1
                i += 1

        elif move == "dr":
            if (j + 1 == "X"):
                i += 1
                j += 1
            else:
                j += 1
                i += 1
        elif move == "dl":
            if (j + 1 == "X"):
                i -= 1
                j += 1
            else:
                j += 1
                i -= 1

        elif move == "L":
            i -= 1

        elif move == "R":
            i += 1

        elif move == "U":
            j -= 1

        elif move == "D":
            j += 1
        pos.add((j, i))

    for j, row in enumerate(maze):
        for i, col in enumerate(row):
            if (j, i) in pos:
                print("", end="")
            else:
                print(col + "", end="")
        print()



def valid(maze, moves):
    for x, pos in enumerate(maze[0]):
        if pos == "S":
            start = x

            i = start
    j = 0
    for move in moves:
        if move == "ul":
            if (j - 1 == "X"):

                i -= 1
                j -= 1
            else:
                j -= 1
                i -= 1

        elif move == "ur":
            if (j - 1 == "X"):
                i += 1
                j -= 1
            else:
                j -= 1
                i += 1

        elif move == "dr":
            if (j + 1 == "X"):
                i += 1
                j += 1
            else:
                j += 1
                i += 1
        elif move == "dl":
            if (j + 1 == "X"):
                i -= 1
                j += 1
            else:
                j += 1
                i -= 1

        elif move == "L":
            i -= 1

        elif move == "R":
            i += 1

        elif move == "U":
            j -= 1

        elif move == "D":
            j += 1

        if not (0 <= i < len(maze[0]) and 0 <= j < len(maze)):
            return False
        elif (maze[j][i] == "X"):
            return False

    return True


def findEnd(maze, moves):
    for x, pos in enumerate(maze[0]):
        if pos == "S":
            start = x

    i = start
    j = 0
    for move in moves:
        if move == "ul":
            if (j - 1 == "X"):

                i -= 1
                j -= 1
            else:
                j -= 1
                i -= 1

        elif move == "ur":
            if (j - 1 == "X"):
                i += 1
                j -= 1
            else:
                j -= 1
                i += 1

        elif move == "dr":
            if (j + 1 == "X"):
                i += 1
                j += 1
            else:
                j += 1
                i += 1
        elif move == "dl":
            if (j + 1 == "X"):
                i -= 1
                j += 1
            else:
                j += 1
                i -= 1

        elif move == "L":
            i -= 1

        elif move == "R":
            i += 1

        elif move == "U":
            j -= 1

        elif move == "D":
            j += 1

    if maze[j][i] == "G":
        print("Found: " + moves)
        printMaze(maze, moves)
        return True

    return False


# MAIN ALGORITHM

nums = queue.Queue() nums.put("") add = "" maze = createMaze2()

while not findEnd(maze, add):
    add = nums.get()
    print(add)
    for j in ["L", "R", "U", "D","ur","ul","dr","dl"]:
        put = add + j
        if valid(maze, put):
            nums.put(put)
评论