地图找出口算法python实现

算法描述

代码实现

import copy

m = [
    [0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, ],
    [1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, ],
    [0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, ],
    [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, ],
    [0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, ],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, ],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, ],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, ],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, ],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, ],
    [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, ],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, ],
    [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, ],
    [0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, ],
    [0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, ],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, ],
]

LEFT = "Left"
RIGHT = "Right"
UP = "Up"
DOWN = "Down"

class Map:
    def __init__(self, m):
        self.m = m
        self.result = copy.deepcopy(m)
        self.current = [0, 0]
        self.direction = RIGHT
        self.height = len(m)
        self.width = len(m[0])
        self.left_translations = dict(Right=UP, Up=LEFT, Left=DOWN, Down=RIGHT)
        self.right_translations = dict(Right=DOWN, Up=RIGHT, Left=UP, Down=LEFT)

    def get_next_position(self, direction):
        if direction == UP:
            return [self.current[0], self.current[1]-1]
        elif direction == RIGHT:
            return [self.current[0]+1, self.current[1]]
        elif direction == DOWN:
            return [self.current[0], self.current[1]+1]
        elif direction == LEFT:
            return [self.current[0]-1, self.current[1]]
        else:
            raise "invalid direction"

    def is_available(self, position) -> bool:
        if position[0] < 0 or position[0] >= self.width or position[1] < 0 or position[1] >= self.height:
            return False
        return self.m[position[1]][position[0]] == 0

    def execute(self):
        step = 1
        self.show(step)
        while True:
            new_direction = self.right_translations[self.direction]
            next_position = self.get_next_position(new_direction)
            if self.is_available(next_position):
                self.direction = new_direction
                if self.has_change(next_position):
                    self.current = next_position
                    step += 1
                    self.show(step)
                    print("-----------------")
            else:
                self.direction = self.left_translations[self.direction]

            if self.finished():
                break
        print("final result")
        self.print_matrix(self.result)

    def finished(self):
        if self.current[0] == len(self.m[1])-1 and self.current[1] == len(self.m)-1:
            return True
        return False

    def has_change(self, new_position):
        return self.current[0] != new_position[0] or self.current[1] != new_position[1]

    def show(self, step):
        print("\n------------------ step : ", step)
        #self.print_matrix(self.m)
        for i in range(len(self.m)):
            for j in range(len(self.m[i])):
                if i == self.current[1] and j == self.current[0]:
                    print("X", end="   ")
                else:
                    print(m[i][j], end="   ")
            print()
        self.result[self.current[1]][self.current[0]] = "X"

    def print_matrix(self, matrix):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == self.current[1] and j == self.current[0]:
                    print("X", end="   ")
                else:
                    print(matrix[i][j], end="   ")
            print()
inst = Map(m)
inst.execute()

执行结果和经过路径